oj.uz

Submission #96629

# Submission time Handle Problem Language Result Execution time Memory
96629 2019-02-10T14:10:07 Z KLPP Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 902 ms 525312 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
vector<int>nei[200000];
int n;
int color[200000];
int dist[200000];
class DSU{
	int parent[200000];
	int size[200000];
	public:
	int isolated;
	void init(int n,int C){isolated=0;
		for(int i=0;i<n;i++){
			if(color[i]==C)size[i]=1,isolated++;
			else size[i]=0;
		}
		for(int i=n;i<2*n-1;i++)size[i]=0;
		for(int i=0;i<2*n-1;i++)parent[i]=i;
	}
	int root(int x){
		if(parent[x]==x)return x;
		parent[x]=root(parent[x]);
		return parent[x];
	}
	void merge(int a, int b){
		a=root(a);
		b=root(b);
		//cout<<a<<" "<<b<<endl;
		if(a==b)return;
		if(size[a]==1 && size[b]!=0)isolated--;
		if(size[b]==1 && size[a]!=0)isolated--;
		if(size[a]<size[b])swap(a,b);
		size[a]+=size[b];
		parent[b]=a;
	}
	void print(int n){
		for(int i=0;i<2*n-1;i++)cout<<parent[i]<<" "<<size[i]<<endl;
	}
};
DSU *D;
queue<int> q;
int solve(int C){
	while(!q.empty())q.pop();
	for(int i=0;i<2*n-1;i++){
		dist[i]=-1;
		if(i<n && color[i]==C){//cout<<i<<endl;
			dist[i]=0;
			q.push(i);
		}
	}
	D->init(n,C);
	
	while(!q.empty() && D->isolated>0){
		int u=q.front();q.pop();
		for(int i=0;i<nei[u].size();i++){
			int v=nei[u][i];
			D->merge(u,v);
			if(dist[v]==-1){
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	//D->print(n);
	if(D->isolated>0)return 1000000000;
	int ans=0;
	for(int i=0;i<2*n-1;i++){
		ans=max(ans,dist[i]);
		//cout<<dist[i]<<endl;
	}
	return ans;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<2*n-1;i++)nei[i].clear();
		for(int i=0;i<n-1;i++){
			int x,y;
			cin>>x>>y;
			x--;y--;
			nei[x].push_back(i+n);
			nei[i+n].push_back(x);
			nei[y].push_back(i+n);
			nei[i+n].push_back(y);			
		}
		for(int i=0;i<n;i++)cin>>color[i];
		int Ds=0;
		D=new DSU();
		Ds=max(Ds,solve(0));
		Ds=max(Ds,solve(1));
		if(Ds>n)cout<<-1<<endl;
		else{
			cout<<Ds<<endl;
			for(int i=0;i<n;i++)cout<<color[i]<<" ";
			cout<<endl;
		}
	}
	return 0;
}

Compilation message

balancedtree.cpp: In function 'int solve(int)':
balancedtree.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nei[u].size();i++){
               ~^~~~~~~~~~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 369 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 402 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Correct 165 ms 12344 KB Output is correct
3 Correct 124 ms 21744 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 335 ms 319624 KB Output isn't correct
2 Incorrect 213 ms 14716 KB Output isn't correct
3 Incorrect 112 ms 17804 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 129 ms 14684 KB Output isn't correct
2 Incorrect 224 ms 162996 KB Invalid color
3 Incorrect 156 ms 83704 KB Invalid color
4 Runtime error 410 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Incorrect 206 ms 147192 KB Output isn't correct
6 Incorrect 125 ms 37112 KB Output isn't correct
7 Incorrect 221 ms 163032 KB Invalid color
8 Runtime error 438 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Incorrect 188 ms 147192 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 369 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 369 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 402 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 165 ms 12344 KB Output is correct
5 Correct 124 ms 21744 KB Output is correct
6 Incorrect 335 ms 319624 KB Output isn't correct
7 Incorrect 213 ms 14716 KB Output isn't correct
8 Incorrect 112 ms 17804 KB Invalid color
9 Incorrect 129 ms 14684 KB Output isn't correct
10 Incorrect 224 ms 162996 KB Invalid color
11 Incorrect 156 ms 83704 KB Invalid color
12 Runtime error 410 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Incorrect 206 ms 147192 KB Output isn't correct
14 Incorrect 125 ms 37112 KB Output isn't correct
15 Incorrect 221 ms 163032 KB Invalid color
16 Runtime error 438 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Incorrect 188 ms 147192 KB Invalid color
18 Incorrect 552 ms 85140 KB Output isn't correct
19 Incorrect 902 ms 22188 KB Output isn't correct
20 Runtime error 386 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 10 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 722 ms 525312 KB Execution killed with signal 11 (could be triggered by violating memory limits)