Submission #96636

#	Time	Username	Problem	Language	Result	Execution time	Memory
96636		KLPP	Balanced Tree (info1cup18_balancedtree)	C++14	13 / 100	4067 ms	15724 KiB

balancedtree

#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]);
		if(n<=17){
			int best[n];
			int ans=1000000001;
			int save[n];
			for(int i=0;i<n;i++)save[i]=color[i];
			for(int msk=0;msk<(1<<n);msk++){
				for(int i=0;i<n;i++){
					if(color[i]==-1){
						color[i]=((msk&(1<<i))>0);
					}
				}
				int can=max(solve(0),solve(1));
				if(can<ans){
					ans=can;
					for(int i=0;i<n;i++){
						best[i]=color[i];
					}
				}
				for(int i=0;i<n;i++)color[i]=save[i];
			}
			if(ans==1000000000){
				printf("-1\n");
			}else{
				printf("%d\n",ans);
				for(int i=0;i<n;i++)printf("%d ",best[i]);
				printf("\n");
			}
		}else{
			int Ds=0;
			Ds=max(Ds,solve(0));
			Ds=max(Ds,solve(1));
			if(Ds>n)printf("-1\n");
			else{
			printf("%d\n",Ds);
			for(int i=0;i<n;i++)printf("%d ",color[i]);
			printf("\n");
			}
		}
	}
	return 0;
}

Compilation message (stderr)

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 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6