Submission #936204

#	Time	Username	Problem	Language	Result	Execution time	Memory
936204		guechotjrhh	Unique Cities (JOI19_ho_t5)	C++14	4 / 100	2094 ms	21564 KiB

joi2019_ho_t5

#include<iostream>
#include<vector>
#include<set>
using namespace std;

void dfs(int i, int p, int d, vector<vector<int>>& vec, vector<vector<int>>& g) {
	vec[d].push_back(i);
	for (int j : g[i]) {
		if (j != p) dfs(j, i, d + 1, vec, g);
	}
}

vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
	vector<int> res(N, -1);
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; i++) {
		g[A[i] - 1].push_back(B[i] - 1);
		g[B[i] - 1].push_back(A[i] - 1);
	}
	for (int i = 0; i < N; i++) {
		vector<vector<int>> vec(N);
		dfs(i, -1, 0, vec, g);
		set<int> st;
		for (int j = 1; j < N; j++) if (vec[j].size() == 1) st.insert(W[vec[j][0]]);
		res[i] = st.size();
	}

	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin >> N >> M;
	vector<int> A(N - 1), B(N - 1);
	for (int i = 0; i < N - 1; i++) {
		cin >> A[i] >> B[i];
	}
	vector<int> W(N);
	for (int i = 0; i < N; i++) {
		cin >> W[i];
	}

	vector<int> ans = find(N, M, A, B, W);

	for (int i = 0; i < N; i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

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