oj.uz

Submission #96711

# Submission time Handle Problem Language Result Execution time Memory
96711 2019-02-11T10:56:23 Z KLPP Balanced Tree (info1cup18_balancedtree) C++14
13 / 100
 1180 ms 23084 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;
	scanf("%d",&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;
			scanf("%d %d",&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++)scanf("%d",&color[i]);
		int save[n];
		for(int i=0;i<n;i++)save[i]=color[i];
		int test0,test1;
		for(int i=0;i<n;i++){
			if(color[i]==-1)color[i]=0;
		}
		test0=max(solve(0),solve(1));
		for(int i=0;i<n;i++)color[i]=save[i];
		for(int i=0;i<n;i++){
			if(color[i]==-1)color[i]=1;
		}test1=max(solve(0),solve(1));
		if(test0==1000000000 && test1==1000000000){
			cout<<-1<<endl;
		}else{
			if(test0>test1){
				cout<<test1<<endl;
				for(int i=0;i<n;i++){
					if(save[i]==-1)cout<<1<<" ";
					else cout<<save[i]<<" ";
				}
			}else{
				cout<<test0<<endl;
				for(int i=0;i<n;i++){
					if(save[i]==-1)cout<<0<<" ";
					else cout<<save[i]<<" ";
				}				
			}
		}
	}
	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++){
               ~^~~~~~~~~~~~~~
balancedtree.cpp: In function 'int main()':
balancedtree.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
  ~~~~~^~~~~~~~~
balancedtree.cpp:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&x,&y);
    ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:91:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<n;i++)scanf("%d",&color[i]);
                       ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6648 KB Output isn't correct
2 Incorrect 12 ms 6648 KB Output isn't correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7544 KB Output is correct
2 Correct 147 ms 12152 KB Output is correct
3 Correct 92 ms 8828 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 7784 KB Output isn't correct
2 Incorrect 176 ms 16428 KB Output isn't correct
3 Incorrect 73 ms 11064 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 9720 KB Output isn't correct
2 Incorrect 75 ms 7860 KB Output isn't correct
3 Incorrect 85 ms 8100 KB Output isn't correct
4 Incorrect 67 ms 7544 KB Output isn't correct
5 Incorrect 59 ms 7800 KB Output isn't correct
6 Incorrect 76 ms 8388 KB Output isn't correct
7 Incorrect 81 ms 7912 KB Output isn't correct
8 Incorrect 64 ms 7544 KB Output isn't correct
9 Incorrect 60 ms 7772 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 6648 KB Output isn't correct
2 Incorrect 12 ms 6648 KB Output isn't correct
3 Correct 71 ms 7544 KB Output is correct
4 Correct 147 ms 12152 KB Output is correct
5 Correct 92 ms 8828 KB Output is correct
6 Incorrect 73 ms 7784 KB Output isn't correct
7 Incorrect 176 ms 16428 KB Output isn't correct
8 Incorrect 73 ms 11064 KB Output isn't correct
9 Incorrect 104 ms 9720 KB Output isn't correct
10 Incorrect 75 ms 7860 KB Output isn't correct
11 Incorrect 85 ms 8100 KB Output isn't correct
12 Incorrect 67 ms 7544 KB Output isn't correct
13 Incorrect 59 ms 7800 KB Output isn't correct
14 Incorrect 76 ms 8388 KB Output isn't correct
15 Incorrect 81 ms 7912 KB Output isn't correct
16 Incorrect 64 ms 7544 KB Output isn't correct
17 Incorrect 60 ms 7772 KB Output isn't correct
18 Incorrect 407 ms 14716 KB Output isn't correct
19 Incorrect 1180 ms 23084 KB Output isn't correct
20 Incorrect 307 ms 11612 KB Output isn't correct
21 Runtime error 14 ms 13048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 138 ms 15708 KB Execution killed with signal 11 (could be triggered by violating memory limits)