提出 #73897873

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

map<int, int> f;
vector<int> a;
vector<vector<int>> g;
vector<bool> dupl;
int duplicates = 0;

void dfs(int node, int parent = 0) {
    f[a[node]]++;
    if (f[a[node]] == 2) ++duplicates;

    dupl[node] = !!duplicates;

    for (int child : g[node]) {
        if (child != parent) dfs(child, node);
    }

    if (f[a[node]] == 2) --duplicates;
    f[a[node]]--;
}

int main() {
    int n; cin >> n;
    a.resize(1+n);
    g.resize(1+n);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dupl.resize(1+n);
    dfs(1);

    for (int k = 1; k <= n; ++k) {
        cout << (dupl[k] ? "Yes" : "No") << '\n';
    }
    return 0;
}

提出情報

提出日時
問題 D - Integer-duplicated Path
ユーザ erekle
言語 C++ IOI-Style(GNU++20) (GCC 14.2.0)
得点 400
コード長 847 Byte
結果 AC
実行時間 646 ms
メモリ 41580 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 3
AC × 47
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hack_01.txt, hack_02.txt, hack_03.txt, hack_04.txt, hack_05.txt, hack_06.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt
ケース名 結果 実行時間 メモリ
hack_01.txt AC 439 ms 27868 KiB
hack_02.txt AC 410 ms 27864 KiB
hack_03.txt AC 149 ms 14228 KiB
hack_04.txt AC 152 ms 14236 KiB
hack_05.txt AC 317 ms 25568 KiB
hack_06.txt AC 324 ms 25560 KiB
sample_01.txt AC 1 ms 1644 KiB
sample_02.txt AC 0 ms 1644 KiB
sample_03.txt AC 0 ms 1644 KiB
test_01.txt AC 1 ms 1644 KiB
test_02.txt AC 1 ms 1644 KiB
test_03.txt AC 628 ms 41580 KiB
test_04.txt AC 620 ms 41580 KiB
test_05.txt AC 597 ms 41580 KiB
test_06.txt AC 569 ms 37740 KiB
test_07.txt AC 266 ms 32108 KiB
test_08.txt AC 255 ms 32108 KiB
test_09.txt AC 363 ms 23576 KiB
test_10.txt AC 339 ms 23572 KiB
test_11.txt AC 330 ms 23572 KiB
test_12.txt AC 273 ms 17300 KiB
test_13.txt AC 159 ms 14228 KiB
test_14.txt AC 180 ms 14232 KiB
test_15.txt AC 435 ms 22764 KiB
test_16.txt AC 455 ms 22764 KiB
test_17.txt AC 473 ms 22764 KiB
test_18.txt AC 481 ms 21612 KiB
test_19.txt AC 234 ms 13420 KiB
test_20.txt AC 231 ms 13420 KiB
test_21.txt AC 449 ms 24300 KiB
test_22.txt AC 401 ms 23276 KiB
test_23.txt AC 376 ms 23916 KiB
test_24.txt AC 264 ms 16236 KiB
test_25.txt AC 222 ms 14060 KiB
test_26.txt AC 204 ms 14828 KiB
test_27.txt AC 646 ms 36716 KiB
test_28.txt AC 548 ms 28652 KiB
test_29.txt AC 601 ms 36332 KiB
test_30.txt AC 516 ms 31212 KiB
test_31.txt AC 253 ms 23404 KiB
test_32.txt AC 258 ms 25836 KiB
test_33.txt AC 551 ms 30188 KiB
test_34.txt AC 568 ms 36972 KiB
test_35.txt AC 537 ms 33388 KiB
test_36.txt AC 426 ms 20332 KiB
test_37.txt AC 285 ms 29292 KiB
test_38.txt AC 230 ms 17644 KiB