oj.uz

Submission #96628

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

using namespace std;
typedef long long int lld;
vector<int>nei[1000000];
int n;
int color[1000000];
int dist[1000000];
class DSU{
	int parent[1000000];
	int size[1000000];
	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 335 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 343 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 373 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Correct 236 ms 43896 KB Output is correct
3 Correct 182 ms 103416 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 389 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 230 ms 39736 KB Output isn't correct
3 Incorrect 176 ms 74104 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 65060 KB Output isn't correct
2 Runtime error 461 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Incorrect 410 ms 417044 KB Invalid color
4 Runtime error 335 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 428 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 242 ms 181112 KB Output isn't correct
7 Runtime error 441 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 333 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 447 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 335 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 343 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 373 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 236 ms 43896 KB Output is correct
5 Correct 182 ms 103416 KB Output is correct
6 Runtime error 389 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 230 ms 39736 KB Output isn't correct
8 Incorrect 176 ms 74104 KB Invalid color
9 Incorrect 175 ms 65060 KB Output isn't correct
10 Runtime error 461 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 410 ms 417044 KB Invalid color
12 Runtime error 335 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 428 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Incorrect 242 ms 181112 KB Output isn't correct
15 Runtime error 441 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 333 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 447 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Incorrect 809 ms 423160 KB Output isn't correct
19 Incorrect 969 ms 72376 KB Output isn't correct
20 Runtime error 340 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Incorrect 1447 ms 72584 KB Output isn't correct
22 Runtime error 433 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)