Submission #1514978
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";
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";
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]<<" ";
}
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 |
2090 Byte |
Status |
WA |
Exec Time |
130 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 |
|
|
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 |
6144 KB |
binary_02.txt |
AC |
85 ms |
6144 KB |
hand_01.txt |
WA |
3 ms |
3072 KB |
hand_02.txt |
AC |
3 ms |
3072 KB |
hand_03.txt |
WA |
3 ms |
3072 KB |
kary_01.txt |
AC |
84 ms |
6784 KB |
kary_02.txt |
WA |
82 ms |
6272 KB |
kary_03.txt |
AC |
80 ms |
6144 KB |
line_01.txt |
AC |
86 ms |
6272 KB |
line_02.txt |
WA |
82 ms |
7168 KB |
line_03.txt |
WA |
86 ms |
7680 KB |
line_04.txt |
WA |
85 ms |
6144 KB |
line_05.txt |
AC |
84 ms |
7808 KB |
line_06.txt |
AC |
85 ms |
6144 KB |
random0_01.txt |
AC |
94 ms |
6272 KB |
random1_01.txt |
WA |
85 ms |
6272 KB |
random1_02.txt |
WA |
86 ms |
6272 KB |
random1_03.txt |
WA |
86 ms |
6272 KB |
random1_04.txt |
WA |
93 ms |
6272 KB |
random1_05.txt |
WA |
86 ms |
6272 KB |
random1_06.txt |
WA |
114 ms |
7680 KB |
random1_07.txt |
WA |
86 ms |
6272 KB |
random1_08.txt |
WA |
130 ms |
7680 KB |
random2_01.txt |
AC |
85 ms |
6272 KB |
random2_02.txt |
AC |
90 ms |
6272 KB |
random2_03.txt |
AC |
85 ms |
6272 KB |
random2_04.txt |
AC |
86 ms |
6272 KB |
random2_05.txt |
AC |
95 ms |
6272 KB |
random2_06.txt |
AC |
112 ms |
7040 KB |
random3_01.txt |
AC |
87 ms |
6272 KB |
random3_02.txt |
AC |
96 ms |
6272 KB |
random4_01.txt |
WA |
85 ms |
6272 KB |
random4_02.txt |
WA |
89 ms |
6272 KB |
random4_03.txt |
WA |
84 ms |
6272 KB |
sample_01.txt |
WA |
3 ms |
3072 KB |
sample_02.txt |
AC |
3 ms |
3072 KB |
sample_03.txt |
WA |
3 ms |
3072 KB |
star_01.txt |
WA |
85 ms |
8056 KB |
star_02.txt |
AC |
72 ms |
7416 KB |