Submission #486291

#	Time	Username	Problem	Language	Result	Execution time	Memory
486291		ez_ioi	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2062 ms	55624 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 1e6 + 5, mod = 1e9 + 7, LOG = 20;

int n, m, c[mxN];

vector <int> adj[mxN], mda[mxN];

void dfs(int v, int par = -1, int d = 0) {
	if (par != -1)
		mda[d].push_back(c[v]);
	for (auto to : adj[v]) {
		if (to != par) 
			dfs(to, v, d + 1);
	}
}

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		adj[u].push_back(v); adj[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) cin >> c[i];
	for (int i = 1; i <= n; ++i) {
		dfs(i);
		set <int> st;
		for (int i = 1; i < n; ++i) {
			if (mda[i].size() == 1) {
				for (auto x : mda[i]) st.insert(x);
			}
			mda[i].clear();
		} 
		cout << (int)st.size() << '\n';
	}
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32