Submission #377952

#	Time	Username	Problem	Language	Result	Execution time	Memory
377952		astoria	Unique Cities (JOI19_ho_t5)	C++14	4 / 100	249 ms	3436 KiB

joi2019_ho_t5

#include "bits/stdc++.h"
using namespace std;

const int N=2005;
int n,m;
vector<int> adj[N];
int c[N];
int dist[N];
vector<int> atD[N];

void dfs(int x, int pa){
	for(int i : adj[x]){
		if(i==pa) continue;
		dist[i]=dist[x]+1;
		atD[dist[i]].push_back(c[i]);
		dfs(i,x);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n>>m;
	for(int i=0; i<n-1; i++){
		int a,b; cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for(int i=1; i<=n; i++) cin>>c[i];
	
	for(int i=1; i<=n; i++){
		memset(dist,-1,sizeof(dist));
		for(int j=0; j<=n; j++) atD[j].clear();
		dist[i]=0;
		dfs(i,-1);
		unordered_set<int> uniq;
		for(int j=1; j<=n; j++){
			//if(i==2) cout<<dist[1]<<"HI"<<endl;
			if(atD[j].size()!=1) continue;
			uniq.insert(atD[j].back());
		}
		cout<<(uniq.size())<<'\n';
	}
}

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