Submission #1515061
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);
}
}
else{
if (flag!=-1){
flag=1-flag;
}
}
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 |
C - 1D Reversi |
User |
Murtlap |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2147 Byte |
Status |
WA |
Exec Time |
3 ms |
Memory |
3072 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:88:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:96:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
^
./Main.cpp:99: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 / 300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
alternate_01.txt, alternate_02.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, same_01.txt, same_02.txt, sample_01.txt, sample_02.txt, sample_03.txt, small_01.txt, small_02.txt, small_03.txt |
Case Name |
Status |
Exec Time |
Memory |
alternate_01.txt |
WA |
3 ms |
3072 KB |
alternate_02.txt |
WA |
3 ms |
3072 KB |
random_01.txt |
WA |
3 ms |
3072 KB |
random_02.txt |
WA |
3 ms |
3072 KB |
random_03.txt |
WA |
3 ms |
3072 KB |
random_04.txt |
WA |
3 ms |
3072 KB |
random_05.txt |
WA |
3 ms |
3072 KB |
same_01.txt |
WA |
3 ms |
3072 KB |
same_02.txt |
WA |
3 ms |
3072 KB |
sample_01.txt |
WA |
3 ms |
3072 KB |
sample_02.txt |
WA |
3 ms |
3072 KB |
sample_03.txt |
WA |
3 ms |
3072 KB |
small_01.txt |
WA |
3 ms |
3072 KB |
small_02.txt |
WA |
3 ms |
3072 KB |
small_03.txt |
WA |
3 ms |
3072 KB |