oj.uz

Submission #67155

# Submission time Handle Problem Language Result Execution time Memory
67155 2018-08-13T12:02:38 Z hamzqq9 Balanced Tree (info1cup18_balancedtree) C++14
23 / 100
 593 ms 20140 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 100005
#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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2680 KB Output is correct
2 Correct 13 ms 2792 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2988 KB Output is correct
2 Correct 107 ms 5292 KB Output is correct
3 Correct 73 ms 5292 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 5292 KB Unexpected end of file - int32 expected
2 Incorrect 83 ms 6404 KB Unexpected end of file - int32 expected
3 Incorrect 49 ms 6404 KB Unexpected end of file - int32 expected

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 6404 KB Invalid color
2 Incorrect 95 ms 6404 KB Invalid color
3 Incorrect 70 ms 6404 KB Output isn't correct
4 Incorrect 54 ms 6404 KB Invalid color
5 Incorrect 50 ms 6404 KB Output isn't correct
6 Incorrect 63 ms 6404 KB Output isn't correct
7 Incorrect 57 ms 6404 KB Invalid color
8 Incorrect 50 ms 6404 KB Output isn't correct
9 Incorrect 45 ms 6404 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2680 KB Output is correct
2 Correct 13 ms 2792 KB Output is correct
3 Correct 51 ms 2988 KB Output is correct
4 Correct 107 ms 5292 KB Output is correct
5 Correct 73 ms 5292 KB Output is correct
6 Incorrect 33 ms 5292 KB Unexpected end of file - int32 expected
7 Incorrect 83 ms 6404 KB Unexpected end of file - int32 expected
8 Incorrect 49 ms 6404 KB Unexpected end of file - int32 expected
9 Incorrect 84 ms 6404 KB Invalid color
10 Incorrect 95 ms 6404 KB Invalid color
11 Incorrect 70 ms 6404 KB Output isn't correct
12 Incorrect 54 ms 6404 KB Invalid color
13 Incorrect 50 ms 6404 KB Output isn't correct
14 Incorrect 63 ms 6404 KB Output isn't correct
15 Incorrect 57 ms 6404 KB Invalid color
16 Incorrect 50 ms 6404 KB Output isn't correct
17 Incorrect 45 ms 6404 KB Invalid color
18 Incorrect 303 ms 6404 KB Output isn't correct
19 Incorrect 593 ms 8836 KB Output isn't correct
20 Incorrect 223 ms 8836 KB Output isn't correct
21 Runtime error 134 ms 20140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 104 ms 20140 KB Execution killed with signal 11 (could be triggered by violating memory limits)