oj.uz

Submission #96636

# Submission time Handle Problem Language Result Execution time Memory
96636 2019-02-10T14:25:52 Z KLPP Balanced Tree (info1cup18_balancedtree) C++14
13 / 100
 4000 ms 15724 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]);
		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

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 Execution timed out 4027 ms 6652 KB Time limit exceeded
2 Execution timed out 4067 ms 6652 KB Time limit exceeded

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6776 KB Output is correct
2 Correct 197 ms 10696 KB Output is correct
3 Correct 83 ms 7672 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 6840 KB Output isn't correct
2 Incorrect 142 ms 14684 KB Output isn't correct
3 Incorrect 61 ms 9976 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 8440 KB Output isn't correct
2 Incorrect 55 ms 6904 KB Invalid color
3 Incorrect 58 ms 7004 KB Invalid color
4 Incorrect 56 ms 6832 KB Invalid color
5 Incorrect 47 ms 6904 KB Output isn't correct
6 Incorrect 65 ms 7132 KB Output isn't correct
7 Incorrect 65 ms 6908 KB Invalid color
8 Incorrect 55 ms 6804 KB Output isn't correct
9 Incorrect 45 ms 6904 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 6652 KB Time limit exceeded
2 Execution timed out 4067 ms 6652 KB Time limit exceeded
3 Correct 57 ms 6776 KB Output is correct
4 Correct 197 ms 10696 KB Output is correct
5 Correct 83 ms 7672 KB Output is correct
6 Incorrect 53 ms 6840 KB Output isn't correct
7 Incorrect 142 ms 14684 KB Output isn't correct
8 Incorrect 61 ms 9976 KB Invalid color
9 Incorrect 74 ms 8440 KB Output isn't correct
10 Incorrect 55 ms 6904 KB Invalid color
11 Incorrect 58 ms 7004 KB Invalid color
12 Incorrect 56 ms 6832 KB Invalid color
13 Incorrect 47 ms 6904 KB Output isn't correct
14 Incorrect 65 ms 7132 KB Output isn't correct
15 Incorrect 65 ms 6908 KB Invalid color
16 Incorrect 55 ms 6804 KB Output isn't correct
17 Incorrect 45 ms 6904 KB Invalid color
18 Incorrect 282 ms 8184 KB Output isn't correct
19 Incorrect 668 ms 15724 KB Output isn't correct
20 Incorrect 228 ms 7544 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 106 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)