提出 #73900906

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
const ll mod = 998244353;

// #include <atcoder/all>
// using mint = atcoder::modint998244353;
// using namespace atcoder;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    
    vector<int> u(n-1), v(n-1);
    for (int i=0; i<n-1; i++) {
      cin >> u[i] >> v[i];
      u[i]--; v[i]--;
    }
    
    vector<vector<int>> graph(n);
    for (int i=0; i<n-1; i++) {
      graph[u[i]].push_back(v[i]);
      graph[v[i]].push_back(u[i]);
    }
    
    vector<bool> ans(n, false);
    int cnt = 0;
    map<int, int> mp;
    
    auto dfs = [&](auto& dfs, int cur, int prev) -> void {
      mp[a[cur]]++;
      if (mp[a[cur]]==2) cnt++;
      if (0<cnt) ans[cur] = true;
      for (int next : graph[cur]) {
        if (next==prev) continue;
        dfs(dfs, next, cur);
      }
      mp[a[cur]]--;
      if (mp[a[cur]]==1) cnt--;
    };
    dfs(dfs, 0, -1);
    
    for (int i=0; i<n; i++) {
      if (ans[i]) cout << "Yes" << endl;
      else cout << "No" << endl;
    }

    return 0;
}

提出情報

提出日時
問題 D - Integer-duplicated Path
ユーザ aonyx64
言語 C++23 (GCC 15.2.0)
得点 400
コード長 1212 Byte
結果 AC
実行時間 408 ms
メモリ 44924 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 324 ms 31200 KiB
hack_02.txt AC 322 ms 31156 KiB
hack_03.txt AC 174 ms 17500 KiB
hack_04.txt AC 174 ms 17476 KiB
hack_05.txt AC 267 ms 28824 KiB
hack_06.txt AC 270 ms 28808 KiB
sample_01.txt AC 1 ms 3508 KiB
sample_02.txt AC 1 ms 3552 KiB
sample_03.txt AC 1 ms 3436 KiB
test_01.txt AC 1 ms 3436 KiB
test_02.txt AC 1 ms 3548 KiB
test_03.txt AC 388 ms 44924 KiB
test_04.txt AC 408 ms 44768 KiB
test_05.txt AC 387 ms 44768 KiB
test_06.txt AC 362 ms 40944 KiB
test_07.txt AC 228 ms 35424 KiB
test_08.txt AC 219 ms 35476 KiB
test_09.txt AC 287 ms 26760 KiB
test_10.txt AC 288 ms 26820 KiB
test_11.txt AC 288 ms 26968 KiB
test_12.txt AC 257 ms 20544 KiB
test_13.txt AC 180 ms 17528 KiB
test_14.txt AC 175 ms 17412 KiB
test_15.txt AC 331 ms 25956 KiB
test_16.txt AC 330 ms 25948 KiB
test_17.txt AC 329 ms 26044 KiB
test_18.txt AC 321 ms 25020 KiB
test_19.txt AC 210 ms 16584 KiB
test_20.txt AC 206 ms 16660 KiB
test_21.txt AC 319 ms 27488 KiB
test_22.txt AC 310 ms 26480 KiB
test_23.txt AC 302 ms 27260 KiB
test_24.txt AC 263 ms 19552 KiB
test_25.txt AC 200 ms 17272 KiB
test_26.txt AC 196 ms 18236 KiB
test_27.txt AC 367 ms 39904 KiB
test_28.txt AC 342 ms 32016 KiB
test_29.txt AC 367 ms 39392 KiB
test_30.txt AC 338 ms 34620 KiB
test_31.txt AC 216 ms 26876 KiB
test_32.txt AC 217 ms 29048 KiB
test_33.txt AC 349 ms 33376 KiB
test_34.txt AC 374 ms 40252 KiB
test_35.txt AC 364 ms 36628 KiB
test_36.txt AC 321 ms 23520 KiB
test_37.txt AC 229 ms 32624 KiB
test_38.txt AC 211 ms 20840 KiB