oj.uz

Submission #96627

# Submission time Handle Problem Language Result Execution time Memory
96627 2019-02-10T14:06:08 Z KLPP Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 1762 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;
	}
};
int solve(int C){
	DSU *D=new DSU();
	queue<int> q;
	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 D=0;
		D=max(D,solve(0));
		D=max(D,solve(1));
		if(D>n)cout<<-1<<endl;
		else cout<<D<<endl;
	}
	return 0;
}

Compilation message

balancedtree.cpp: In function 'int solve(int)':
balancedtree.cpp:56: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 874 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 374 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 434 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 217 ms 60448 KB Invalid color
3 Incorrect 272 ms 182488 KB Invalid color

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 424 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Incorrect 207 ms 48888 KB Output isn't correct
3 Incorrect 177 ms 121980 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 105052 KB Output isn't correct
2 Runtime error 392 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 444 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 350 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 393 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Incorrect 349 ms 338680 KB Output isn't correct
7 Runtime error 411 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 363 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 360 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 874 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 374 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 434 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Incorrect 217 ms 60448 KB Invalid color
5 Incorrect 272 ms 182488 KB Invalid color
6 Runtime error 424 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Incorrect 207 ms 48888 KB Output isn't correct
8 Incorrect 177 ms 121980 KB Invalid color
9 Incorrect 329 ms 105052 KB Output isn't correct
10 Runtime error 392 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 444 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 350 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 393 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Incorrect 349 ms 338680 KB Output isn't correct
15 Runtime error 411 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 363 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 360 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 715 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Incorrect 1006 ms 117012 KB Output isn't correct
20 Runtime error 425 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Incorrect 1762 ms 85256 KB Output isn't correct
22 Runtime error 401 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)