oj.uz

Submission #96630

# Submission time Handle Problem Language Result Execution time Memory
96630 2019-02-10T14:11:13 Z KLPP Balanced Tree (info1cup18_balancedtree) C++14
13 / 100
 888 ms 15892 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;
	D=new DSU();
	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;
		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 Incorrect 12 ms 6648 KB Invalid color
2 Incorrect 16 ms 6648 KB Invalid color

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7672 KB Output is correct
2 Correct 187 ms 10796 KB Output is correct
3 Correct 111 ms 7672 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 6776 KB Output isn't correct
2 Incorrect 207 ms 14712 KB Output isn't correct
3 Incorrect 105 ms 9820 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 8440 KB Output isn't correct
2 Incorrect 89 ms 6864 KB Invalid color
3 Incorrect 95 ms 7004 KB Invalid color
4 Incorrect 84 ms 7652 KB Invalid color
5 Incorrect 79 ms 6904 KB Output isn't correct
6 Incorrect 95 ms 7132 KB Output isn't correct
7 Incorrect 93 ms 7032 KB Invalid color
8 Incorrect 82 ms 7544 KB Output isn't correct
9 Incorrect 76 ms 6904 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6648 KB Invalid color
2 Incorrect 16 ms 6648 KB Invalid color
3 Correct 87 ms 7672 KB Output is correct
4 Correct 187 ms 10796 KB Output is correct
5 Correct 111 ms 7672 KB Output is correct
6 Incorrect 86 ms 6776 KB Output isn't correct
7 Incorrect 207 ms 14712 KB Output isn't correct
8 Incorrect 105 ms 9820 KB Invalid color
9 Incorrect 119 ms 8440 KB Output isn't correct
10 Incorrect 89 ms 6864 KB Invalid color
11 Incorrect 95 ms 7004 KB Invalid color
12 Incorrect 84 ms 7652 KB Invalid color
13 Incorrect 79 ms 6904 KB Output isn't correct
14 Incorrect 95 ms 7132 KB Output isn't correct
15 Incorrect 93 ms 7032 KB Invalid color
16 Incorrect 82 ms 7544 KB Output isn't correct
17 Incorrect 76 ms 6904 KB Invalid color
18 Incorrect 531 ms 8336 KB Output isn't correct
19 Incorrect 888 ms 15892 KB Output isn't correct
20 Incorrect 379 ms 11548 KB Output isn't correct
21 Runtime error 13 ms 12920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 241 ms 15872 KB Execution killed with signal 11 (could be triggered by violating memory limits)