답안 #67154 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67154	2018-08-13T12:02:04 Z	hamzqq9	Balanced Tree (info1cup18_balancedtree)	C++14	10 / 100	240 ms	2024 KB

balancedtree

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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)

답안 #67154

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 0.0 / 13.0

Subtask #3 0.0 / 26.0

Subtask #4 0.0 / 45.0

Subtask #5 0.0 / 6.0

Subtask #1
10.0 / 10.0

Subtask #2
0.0 / 13.0

Subtask #3
0.0 / 26.0

Subtask #4
0.0 / 45.0

Subtask #5
0.0 / 6.0