Submission #73916454

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define str string
#define db double
using namespace std;
constexpr ll MAXN = 2e5 + 5;
ll n, a[MAXN];
bool can[MAXN];
vector<ll> vec[MAXN];
unordered_map<ll, ll> mp;

void dfs(ll now, ll fa, bool yes) {
	if (mp[a[now]])
		yes = true;
	mp[a[now]]++;
	for (const auto& v : vec[now])
		if (v != fa)
			dfs(v, now, yes);
	mp[a[now]]--, can[now] = yes;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n;
	for (ll i = 1; i <= n; i++)
		cin >> a[i];
	for (ll i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		vec[u].emplace_back(v);
		vec[v].emplace_back(u);
	}
	dfs(1, 0, 0);
	for (ll i = 1; i <= n; i++)
		cout << (can[i] ? "Yes" : "No") << '\n';
	return 0;
}

Submission Info

Submission Time
Task D - Integer-duplicated Path
User a_legend_cat
Language C++ IOI-Style(GNU++20) (GCC 14.2.0)
Score 400
Code Size 776 Byte
Status AC
Exec Time 165 ms
Memory 38908 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 47
Set Name Test Cases
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
Case Name Status Exec Time Memory
hack_01.txt AC 114 ms 27432 KiB
hack_02.txt AC 112 ms 27428 KiB
hack_03.txt AC 58 ms 15868 KiB
hack_04.txt AC 61 ms 15876 KiB
hack_05.txt AC 97 ms 25156 KiB
hack_06.txt AC 102 ms 25284 KiB
sample_01.txt AC 1 ms 1584 KiB
sample_02.txt AC 1 ms 1584 KiB
sample_03.txt AC 1 ms 1584 KiB
test_01.txt AC 1 ms 1584 KiB
test_02.txt AC 1 ms 1584 KiB
test_03.txt AC 163 ms 38908 KiB
test_04.txt AC 163 ms 38900 KiB
test_05.txt AC 165 ms 38908 KiB
test_06.txt AC 145 ms 35000 KiB
test_07.txt AC 122 ms 29872 KiB
test_08.txt AC 124 ms 30000 KiB
test_09.txt AC 100 ms 25344 KiB
test_10.txt AC 99 ms 25344 KiB
test_11.txt AC 102 ms 25344 KiB
test_12.txt AC 72 ms 18684 KiB
test_13.txt AC 62 ms 15872 KiB
test_14.txt AC 64 ms 15908 KiB
test_15.txt AC 151 ms 25408 KiB
test_16.txt AC 146 ms 25408 KiB
test_17.txt AC 139 ms 25412 KiB
test_18.txt AC 135 ms 25404 KiB
test_19.txt AC 94 ms 16560 KiB
test_20.txt AC 97 ms 16688 KiB
test_21.txt AC 141 ms 27008 KiB
test_22.txt AC 115 ms 25336 KiB
test_23.txt AC 123 ms 25896 KiB
test_24.txt AC 86 ms 18096 KiB
test_25.txt AC 82 ms 16560 KiB
test_26.txt AC 72 ms 17200 KiB
test_27.txt AC 152 ms 35948 KiB
test_28.txt AC 140 ms 29696 KiB
test_29.txt AC 157 ms 35740 KiB
test_30.txt AC 139 ms 30484 KiB
test_31.txt AC 113 ms 23728 KiB
test_32.txt AC 111 ms 25520 KiB
test_33.txt AC 147 ms 30960 KiB
test_34.txt AC 156 ms 36116 KiB
test_35.txt AC 150 ms 33428 KiB
test_36.txt AC 111 ms 21708 KiB
test_37.txt AC 116 ms 28080 KiB
test_38.txt AC 96 ms 18864 KiB