oj.uz

Submission #120625

# Submission time Handle Problem Language Result Execution time Memory
120625 2019-06-25T06:12:18 Z 임유진(#2961) Mergers (JOI19_mergers) C++14
0 / 100
 94 ms 50284 KB 
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 500005

int A[MAXN], B[MAXN], S[MAXN];
vector<int> e[MAXN];
int par[20][MAXN], dep[MAXN];
vector<int> ss[MAXN];
bool chkn[MAXN], chks[MAXN];
queue<int> q;
int gs[MAXN];
vector<int> ge[MAXN];

void dfs(int x){
	for(auto a:e[x]) if(a!=par[0][x]){
		par[0][a]=x;
		dep[a]=dep[x]+1;
		dfs(a);
	}
}

int anc(int x, int d){
	if(d>dep[x]) return 0;
	for(int i=19; i>=0; i--) if((dep[x]-d)&(1<<i)) x=par[i][x];
	return x;
}

int lca(int x, int y){
	if(dep[x]>dep[y]) x=anc(x, dep[y]);
	else y=anc(y, dep[x]);
	if(x==y) return x;
	for(int i=19; i>=0; i--) if(par[i][x]!=par[i][y]){
		x=par[i][x];
		y=par[i][y];
	}
	return par[0][x];
}

int main(){
	int N, K;
	int ans=0;

	scanf("%d%d", &N, &K);
	for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
	for(int i=1; i<=N; i++) scanf("%d", S+i);

	for(int i=0; i<N-1; i++){
		e[A[i]].push_back(B[i]);
		e[B[i]].push_back(A[i]);
	}
	par[0][1]=1;
	dfs(1);
	for(int i=1; i<20; i++) for(int j=1; j<=N; j++) par[i][j]=par[i-1][par[i-1][j]];
	//for(int i=1; i<=N; i++) printf("%d %d %d\n", par[0][i], par[1][i], par[2][i]);
	for(int i=1; i<=N; i++) ss[S[i]].push_back(i);
	//for(int i=1; i<=K; i++) printf("%d\n", ss[i].size());
	
	for(int i=1; i<=K; i++) if(!chks[i]){
		chks[i]=true;
		q.push(i);
		//printf("[%d]\n", i);
		while(!q.empty()){
			int t=q.front();
			q.pop();
			gs[t]=i;
			int l=ss[t][0];
			for(auto a:ss[t]) l=lca(l, a);
			//printf("lca=%d\n", l);
			for(auto a:ss[t]) for(int j=a; dep[j]>=dep[l]&&!chkn[j]; j=par[0][j]){
				chkn[j]=true;
				if(!chks[S[j]]){
					chks[S[j]]=true;
					q.push(S[j]);
				}
			}
		}
	}

	//for(int i=1; i<=K; i++) printf("%d ", gs[i]);

	for(int i=0; i<N-1; i++) if(gs[S[A[i]]]!=gs[S[B[i]]]){
		ge[gs[S[A[i]]]].push_back(gs[S[B[i]]]);
		ge[gs[S[B[i]]]].push_back(gs[S[A[i]]]);
		//printf("(%d %d)\n", S[A[i]], S[B[i]]);
	}
	for(int i=1; i<=K; i++){
		sort(ge[i].begin(), ge[i].end());
		if(unique(ge[i].begin(), ge[i].end())-ge[i].begin()==1) ans++;
	}

	//printf("\n%d\n", ans);
	printf("%d", (ans+1)/2);
	return 0;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
mergers.cpp:49:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N-1; i++) scanf("%d%d", A+i, B+i);
                           ~~~~~^~~~~~~~~~~~~~~~~~
mergers.cpp:50:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", S+i);
                          ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35712 KB Output is correct
2 Correct 32 ms 35840 KB Output is correct
3 Correct 32 ms 35832 KB Output is correct
4 Correct 31 ms 35712 KB Output is correct
5 Incorrect 31 ms 35704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35712 KB Output is correct
2 Correct 32 ms 35840 KB Output is correct
3 Correct 32 ms 35832 KB Output is correct
4 Correct 31 ms 35712 KB Output is correct
5 Incorrect 31 ms 35704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35712 KB Output is correct
2 Correct 32 ms 35840 KB Output is correct
3 Correct 32 ms 35832 KB Output is correct
4 Correct 31 ms 35712 KB Output is correct
5 Incorrect 31 ms 35704 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 50284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35712 KB Output is correct
2 Correct 32 ms 35840 KB Output is correct
3 Correct 32 ms 35832 KB Output is correct
4 Correct 31 ms 35712 KB Output is correct
5 Incorrect 31 ms 35704 KB Output isn't correct
6 Halted 0 ms 0 KB -