답안 #67141 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67141	2018-08-13T11:42:22 Z	hamzqq9	Balanced Tree (info1cup18_balancedtree)	C++14	0 / 100	145 ms	1108 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 S2() {}

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

	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]);				

			}

		}

	}

	for(int i:v[node]) {

		if(i==ata) continue ;

		NEN[0]=(mn[0][0]==NE[i][0]+1?mn[0][1]:mn[0][0])+1;
		NEN[1]=(mn[1][0]==NE[i][1]+1?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;


	}

}

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 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:185:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
balancedtree.cpp:189: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:196: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:210: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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	7 ms	376 KB	Output isn't correct
2	Incorrect	9 ms	488 KB	Output isn't correct

Subtask #2
0.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	32 ms	488 KB	Unexpected end of file - int32 expected
2	Runtime error	3 ms	584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	4 ms	700 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	37 ms	700 KB	Unexpected end of file - int32 expected
2	Runtime error	2 ms	768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	3 ms	908 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	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Incorrect	36 ms	908 KB	Unexpected end of file - int32 expected
3	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Incorrect	46 ms	908 KB	Unexpected end of file - int32 expected
5	Incorrect	31 ms	908 KB	Unexpected end of file - int32 expected
6	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Incorrect	38 ms	920 KB	Unexpected end of file - int32 expected
8	Incorrect	30 ms	920 KB	Unexpected end of file - int32 expected
9	Incorrect	33 ms	920 KB	Unexpected end of file - int32 expected

Subtask #5
0.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	7 ms	376 KB	Output isn't correct
2	Incorrect	9 ms	488 KB	Output isn't correct
3	Incorrect	32 ms	488 KB	Unexpected end of file - int32 expected
4	Runtime error	3 ms	584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	4 ms	700 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Incorrect	37 ms	700 KB	Unexpected end of file - int32 expected
7	Runtime error	2 ms	768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Incorrect	36 ms	908 KB	Unexpected end of file - int32 expected
11	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Incorrect	46 ms	908 KB	Unexpected end of file - int32 expected
13	Incorrect	31 ms	908 KB	Unexpected end of file - int32 expected
14	Runtime error	3 ms	908 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Incorrect	38 ms	920 KB	Unexpected end of file - int32 expected
16	Incorrect	30 ms	920 KB	Unexpected end of file - int32 expected
17	Incorrect	33 ms	920 KB	Unexpected end of file - int32 expected
18	Runtime error	3 ms	920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	3 ms	920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Incorrect	145 ms	1036 KB	Unexpected end of file - int32 expected
21	Runtime error	4 ms	1036 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Runtime error	77 ms	1108 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #67141

Compilation message

Subtask #1 0.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
0.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