oj.uz

Submission #120631

# Submission time Handle Problem Language Result Execution time Memory
120631 2019-06-25T06:28:19 Z 임유진(#2961) Mergers (JOI19_mergers) C++14
0 / 100
 181 ms 55936 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 uni(int x){
	if(gs[x]==x) return x;
	return gs[x]=uni(gs[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++) gs[i]=i;
	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();
			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]&&(j==a||uni(S[j])!=uni(i)); j=par[0][j]){
				//printf("[%d %d]\n", i, j);
				gs[uni(S[j])]=uni(i);
				chkn[j]=true;
				if(!chks[S[j]]){
					chks[S[j]]=true;
					q.push(S[j]);
				}
				if(j==1) break;
			}
		}
	}

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

	for(int i=1; i<=K; i++) gs[i]=uni(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(distance(ge[i].begin(), unique(ge[i].begin(), ge[i].end()))==1) ans++;
	}

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

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:53: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:54: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:55: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 35704 KB Output is correct
2 Correct 32 ms 35748 KB Output is correct
3 Correct 31 ms 35712 KB Output is correct
4 Correct 32 ms 35712 KB Output is correct
5 Correct 31 ms 35704 KB Output is correct
6 Correct 31 ms 35832 KB Output is correct
7 Correct 32 ms 35684 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 33 ms 35704 KB Output is correct
10 Correct 32 ms 35712 KB Output is correct
11 Correct 31 ms 35704 KB Output is correct
12 Correct 32 ms 35704 KB Output is correct
13 Incorrect 31 ms 35704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35704 KB Output is correct
2 Correct 32 ms 35748 KB Output is correct
3 Correct 31 ms 35712 KB Output is correct
4 Correct 32 ms 35712 KB Output is correct
5 Correct 31 ms 35704 KB Output is correct
6 Correct 31 ms 35832 KB Output is correct
7 Correct 32 ms 35684 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 33 ms 35704 KB Output is correct
10 Correct 32 ms 35712 KB Output is correct
11 Correct 31 ms 35704 KB Output is correct
12 Correct 32 ms 35704 KB Output is correct
13 Incorrect 31 ms 35704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35704 KB Output is correct
2 Correct 32 ms 35748 KB Output is correct
3 Correct 31 ms 35712 KB Output is correct
4 Correct 32 ms 35712 KB Output is correct
5 Correct 31 ms 35704 KB Output is correct
6 Correct 31 ms 35832 KB Output is correct
7 Correct 32 ms 35684 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 33 ms 35704 KB Output is correct
10 Correct 32 ms 35712 KB Output is correct
11 Correct 31 ms 35704 KB Output is correct
12 Correct 32 ms 35704 KB Output is correct
13 Incorrect 31 ms 35704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 49328 KB Output is correct
2 Correct 149 ms 55936 KB Output is correct
3 Correct 33 ms 36224 KB Output is correct
4 Correct 34 ms 36220 KB Output is correct
5 Correct 31 ms 35712 KB Output is correct
6 Correct 32 ms 35704 KB Output is correct
7 Correct 34 ms 36224 KB Output is correct
8 Incorrect 181 ms 50652 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35704 KB Output is correct
2 Correct 32 ms 35748 KB Output is correct
3 Correct 31 ms 35712 KB Output is correct
4 Correct 32 ms 35712 KB Output is correct
5 Correct 31 ms 35704 KB Output is correct
6 Correct 31 ms 35832 KB Output is correct
7 Correct 32 ms 35684 KB Output is correct
8 Correct 32 ms 35704 KB Output is correct
9 Correct 33 ms 35704 KB Output is correct
10 Correct 32 ms 35712 KB Output is correct
11 Correct 31 ms 35704 KB Output is correct
12 Correct 32 ms 35704 KB Output is correct
13 Incorrect 31 ms 35704 KB Output isn't correct
14 Halted 0 ms 0 KB -