Submission #1515014


Source Code Expand

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int n,k;
vector<int> G[100005];
int val[100005];
bool vis[100005];
pair<int,int> dp[100005];
void check(int x,int flag){
	vis[x]=true;
	if (val[x]!=-1){
		if (flag==-1){
			flag=1-(val[x]%2);
		}
		else if (val[x]%2!=flag){
			cout<<"No\n";
			exit(0);
		}
		else{
			flag=1-(val[x]%2);
		}
	}
	for (int i=0;i<G[x].size();i++){
		if (vis[G[x][i]]){
			continue;
		}
		check(G[x][i],flag);
	}
}
pair<int,int> get(pair<int,int> a,pair<int,int> b){
	if (a.first==-1e9 || b.first==-1e9){
		return make_pair(-1e9,-1e9);
	}
	if (a.first>b.first){
		swap(a,b);
	}
	if (a.second<b.first){
		return make_pair(-1e9,-1e9);
	}
	else{
		return make_pair(b.first,min(a.second,b.second));
	}
}
void dfs(int x){
	vis[x]=true;
	int left=-1e8;
	int right=1e8;
	vector<int> V;
	if (val[x]!=-1){
		left=val[x];
		right=val[x];
	}
	for (int i=0;i<G[x].size();i++){
		if (vis[G[x][i]]){
			continue;
		}
		dfs(G[x][i]);
		pair<int,int> tmp=get(make_pair(left,right),make_pair(dp[G[x][i]].first-1,dp[G[x][i]].second+1));
		left=tmp.first;
		right=tmp.second;
	}
	if (left==-1e9){
		cout<<"No\n";
		exit(0);
	}
	dp[x]=make_pair(left,right);
}
void Dfs(int x,int left,int right){
	dp[x]=get(dp[x],make_pair(left,right));
	val[x]=dp[x].first;
	vis[x]=true;
	for (int i=0;i<G[x].size();i++){
		if (vis[G[x][i]]){
			continue;
		}
		Dfs(G[x][i],val[x]-1,val[x]+1);
	}
}
int main(){
	scanf("%d",&n);
    for (int i=1;i<=n-1;i++){
    	int a,b;
    	cin>>a>>b;
    	G[a].push_back(b);
    	G[b].push_back(a);
    }
    memset(val,-1,sizeof(val));
    scanf("%d",&k);
    for (int i=1;i<=k;i++){
    	int node,v;
    	scanf("%d%d",&node,&v);
    	val[node]=v;
    }
    memset(vis,0,sizeof(vis));
    check(1,-1);
    memset(vis,0,sizeof(vis));
    dfs(1);
    cout<<"Yes\n";
    memset(vis,0,sizeof(vis));
    Dfs(1,-1e8,1e8);
    for (int i=1;i<=n;i++){
    	cout<<val[i]<<endl;
    }
    return 0;
}

Submission Info

Submission Time
Task E - Integers on a Tree
User Murtlap
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2095 Byte
Status WA
Exec Time 275 ms
Memory 8056 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:91:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
                   ^
./Main.cpp:94:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&node,&v);
                            ^

Judge Result

Set Name sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 24
WA × 15
Set Name Test Cases
sample sample_01.txt, sample_02.txt, sample_03.txt
All binary_01.txt, binary_02.txt, hand_01.txt, hand_02.txt, hand_03.txt, kary_01.txt, kary_02.txt, kary_03.txt, line_01.txt, line_02.txt, line_03.txt, line_04.txt, line_05.txt, line_06.txt, random0_01.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, random1_08.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random3_01.txt, random3_02.txt, random4_01.txt, random4_02.txt, random4_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt
Case Name Status Exec Time Memory
binary_01.txt WA 92 ms 6272 KB
binary_02.txt AC 83 ms 6272 KB
hand_01.txt AC 3 ms 3072 KB
hand_02.txt AC 3 ms 3072 KB
hand_03.txt WA 3 ms 3072 KB
kary_01.txt AC 86 ms 6784 KB
kary_02.txt WA 80 ms 6272 KB
kary_03.txt AC 81 ms 6144 KB
line_01.txt AC 86 ms 6144 KB
line_02.txt WA 83 ms 7168 KB
line_03.txt WA 82 ms 7680 KB
line_04.txt WA 87 ms 6272 KB
line_05.txt AC 82 ms 7808 KB
line_06.txt AC 87 ms 6144 KB
random0_01.txt AC 93 ms 6272 KB
random1_01.txt WA 87 ms 6272 KB
random1_02.txt WA 85 ms 6272 KB
random1_03.txt WA 87 ms 6272 KB
random1_04.txt WA 93 ms 6272 KB
random1_05.txt WA 88 ms 6272 KB
random1_06.txt AC 261 ms 7808 KB
random1_07.txt WA 86 ms 6272 KB
random1_08.txt AC 275 ms 7680 KB
random2_01.txt AC 86 ms 6272 KB
random2_02.txt AC 88 ms 6272 KB
random2_03.txt AC 96 ms 6272 KB
random2_04.txt AC 86 ms 6272 KB
random2_05.txt AC 95 ms 6272 KB
random2_06.txt AC 110 ms 7040 KB
random3_01.txt AC 87 ms 6272 KB
random3_02.txt AC 93 ms 6272 KB
random4_01.txt WA 88 ms 6272 KB
random4_02.txt WA 86 ms 6272 KB
random4_03.txt WA 85 ms 6272 KB
sample_01.txt AC 3 ms 3072 KB
sample_02.txt AC 3 ms 3072 KB
sample_03.txt AC 3 ms 3072 KB
star_01.txt AC 228 ms 8056 KB
star_02.txt AC 73 ms 7416 KB