oj.uz

Submission #67152

# Submission time Handle Problem Language Result Execution time Memory
67152 2018-08-13T12:00:49 Z hamzqq9 Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 359 ms 1780 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 2000000000
#define MOD 1000000007
#define N 1005
#define MAX 10000006
#define LOG 22
using namespace std;

int n,x,y,T;
int NE[N][2];
int ans,cev;
int c[N],temp[N];
vector<int> v[N];

void S3() {}

void NDFS(int node,int ata,int NEE[]) {

/*	printf("%d\n",node);

	for(int i=0;i<2;i++) printf("%d ",NEE[i]);

	printf("\n----------\n");*/

	int NEN[2];

	umax(ans,min(NEE[c[node]],NE[node][c[node]]));

	int mn[2][2]={NEE[0],inf,NEE[1],inf};

	swap(mn[c[node]][0],mn[c[node]][1]);

	mn[c[node]][0]=0;

	for(int i:v[node]) {

		if(i==ata) continue ;

		for(int j=0;j<2;j++) {

			if(NE[i][j]+1<mn[j][1]) {

				mn[j][1]=NE[i][j]+1;

				if(mn[j][1]<mn[j][0]) swap(mn[j][1],mn[j][0]);				

			}

		}

		if(1<mn[c[i]][1]) {

			mn[c[i]][1]=1;

			if(mn[c[i]][1]>mn[c[i]][0]) swap(mn[c[i]][1],mn[c[i]][0]);

		}

	}

	for(int i:v[node]) {

		if(i==ata) continue ;

		int t0=(c[i]==0?1:NE[i][0]+1);
		int t1=(c[i]==1?1:NE[i][1]+1);

		NEN[0]=(mn[0][0]==t0?mn[0][1]:mn[0][0])+1;
		NEN[1]=(mn[1][0]==t1?mn[1][1]:mn[1][0])+1;

		NDFS(i,node,NEN);

	}

}

void SDFS(int node,int ata) {

	NE[node][c[node]]=inf;

	NE[node][!c[node]]=inf;

	for(int i:v[node]) {

		if(i==ata) continue ;

		SDFS(i,node);

		umin(NE[node][0],NE[i][0]+1);

		if(c[i]==0) NE[node][0]=1;

		umin(NE[node][1],NE[i][1]+1);

		if(c[i]==1) NE[node][1]=1;


	}

//	printf("node-->%d ne0-->%d ne1-->%d\n",node,NE[node][0],NE[node][1]);

}

void back_track(int now) {

	if(now>n) {

		SDFS(1,0);

		int NE[2];

		NE[0]=NE[1]=inf;

		ans=0;

		NDFS(1,0,NE);

		if(cev>ans) {

			cev=ans;

			for(int i=1;i<=n;i++) temp[i]=c[i];

		}

		return ;

	}

	if(c[now]!=-1) back_track(now+1);
	else {

		c[now]=1;

		back_track(now+1);

		c[now]=0;

		back_track(now+1);

		c[now]=-1;

	}

}

void S2() {

	SDFS(1,0);

	int NE[2];

	NE[0]=NE[1]=inf;

	ans=0;

	NDFS(1,0,NE);

	if(ans==inf) {

		printf("-1\n");

		return ;

	}

	printf("%d\n",ans);

	for(int i=1;i<=n;i++) printf("%d ",c[i]);

	puts(""); 

}

void S1() {

	cev=inf;

	back_track(1);

	if(cev==inf) {

		printf("-1\n");

		return ;

	}

	printf("%d\n",cev);

	for(int i=1;i<=n;i++) printf("%d ",temp[i]);

	puts("");

}

bool is_path() {

	int leaf=0;

	for(int i=1;i<=n;i++) {

		if(sz(v[i])>2) return false;

		if(sz(v[i])==1) leaf++;

	}

	return (n==1 || leaf==2);

}

void read() {

	scanf("%d",&n);

	for(int i=1;i<n;i++) {

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}

	for(int i=1;i<=n;i++) scanf("%d",&c[i]);

}

void clear() {

	for(int i=1;i<=n;i++) v[i].clear();

}

int main() {
 
	//freopen("input.txt","r",stdin);
 
	scanf("%d",&T);

	for(int t=1;t<=T;t++) {

		read();

		if(T<=500 && n<=17) S1();
		else if(is_path()) S3();
		else S2();

		clear();

	}


}

Compilation message

balancedtree.cpp: In function 'void read()':
balancedtree.cpp:230:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
balancedtree.cpp:234:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
balancedtree.cpp:241:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&c[i]);
                        ~~~~~^~~~~~~~~~~~
balancedtree.cpp: In function 'int main()':
balancedtree.cpp:255:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&T);
  ~~~~~^~~~~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Incorrect 13 ms 484 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 680 KB Output isn't correct
2 Runtime error 2 ms 712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 804 KB Unexpected end of file - int32 expected
2 Runtime error 3 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 61 ms 1216 KB Invalid color
3 Runtime error 2 ms 1216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 54 ms 1216 KB Output isn't correct
5 Incorrect 41 ms 1228 KB Output isn't correct
6 Runtime error 3 ms 1228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 59 ms 1272 KB Output isn't correct
8 Incorrect 62 ms 1272 KB Output isn't correct
9 Incorrect 51 ms 1272 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 376 KB Output isn't correct
2 Incorrect 13 ms 484 KB Output isn't correct
3 Incorrect 44 ms 680 KB Output isn't correct
4 Runtime error 2 ms 712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 37 ms 804 KB Unexpected end of file - int32 expected
7 Runtime error 3 ms 804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 61 ms 1216 KB Invalid color
11 Runtime error 2 ms 1216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 54 ms 1216 KB Output isn't correct
13 Incorrect 41 ms 1228 KB Output isn't correct
14 Runtime error 3 ms 1228 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 59 ms 1272 KB Output isn't correct
16 Incorrect 62 ms 1272 KB Output isn't correct
17 Incorrect 51 ms 1272 KB Invalid color
18 Runtime error 3 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 1272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 359 ms 1780 KB Output isn't correct
21 Runtime error 3 ms 1780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 116 ms 1780 KB Execution killed with signal 11 (could be triggered by violating memory limits)