oj.uz

Submission #67154

# Submission time Handle Problem Language Result Execution time Memory
67154 2018-08-13T12:02:04 Z hamzqq9 Balanced Tree (info1cup18_balancedtree) C++14
10 / 100
 240 ms 2024 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 14 ms 504 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 584 KB Output is correct
2 Runtime error 3 ms 712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 3 ms 712 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 38 ms 760 KB Unexpected end of file - int32 expected
2 Runtime error 3 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 976 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 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 71 ms 1108 KB Invalid color
3 Runtime error 3 ms 1108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 64 ms 1344 KB Invalid color
5 Incorrect 48 ms 1344 KB Output isn't correct
6 Runtime error 3 ms 1344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 67 ms 1344 KB Invalid color
8 Incorrect 84 ms 1344 KB Output isn't correct
9 Incorrect 47 ms 1344 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 14 ms 504 KB Output is correct
3 Correct 60 ms 584 KB Output is correct
4 Runtime error 3 ms 712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 38 ms 760 KB Unexpected end of file - int32 expected
7 Runtime error 3 ms 792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 4 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 71 ms 1108 KB Invalid color
11 Runtime error 3 ms 1108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 64 ms 1344 KB Invalid color
13 Incorrect 48 ms 1344 KB Output isn't correct
14 Runtime error 3 ms 1344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 67 ms 1344 KB Invalid color
16 Incorrect 84 ms 1344 KB Output isn't correct
17 Incorrect 47 ms 1344 KB Invalid color
18 Runtime error 3 ms 1344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 3 ms 1344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 240 ms 2024 KB Output isn't correct
21 Runtime error 3 ms 2024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 100 ms 2024 KB Execution killed with signal 11 (could be triggered by violating memory limits)