Submission #972322
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; typedef pair<int,int> pii; const pii inf=make_pair(-1e7,1e7); const pii fail=make_pair(1e7,-1e7); vector<pii> range; vector<int> edge[100000]; bool visited[100000]; pii dfs(int v){ if(visited[v]) return inf; visited[v]=true; for(int i=0;i<edge[v].size();i++){ int to=edge[v][i]; pii result=dfs(edge[v][i]); if(result==make_pair(inf.first-1,inf.second+1)) result=inf; if(result==fail) return fail; else if(range[v]==inf) range[v]=result; else if(result==inf) continue; else if(range[v].first%2!=result.first%2) return fail; else if(range[v].second<result.first) return fail; else if(result.second<range[v].first) return fail; else{ range[v].second=min(range[v].second,result.second); range[v].first=max(range[v].first,result.first); } } if(range[v].second<range[v].first) return fail; return make_pair(range[v].first-1,range[v].second+1); } void decide(int v){ if(visited[v]) return; visited[v]=true; range[v]=make_pair(range[v].first,range[v].first); for(int i=0;i<edge[v].size();i++){ int to=edge[v][i]; if(visited[to]) continue; range[to]=make_pair(max(range[to].first,range[v].first-1), min(range[to].second,range[v].second+1)); decide(to); } return; } int main(){ int n; cin>>n; for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; a--; b--; edge[a].push_back(b); edge[b].push_back(a); } for(int i=0;i<n;i++) visited[i]=false; range=vector<pii>(n,inf); int k; cin>>k; for(int i=0;i<k;i++){ int v,p; cin>>v>>p; v--; range[v]=make_pair(p,p); } pii ret=dfs(0); if(ret==fail){ cout<<"No"<<endl; return 0; } cout<<"Yes"<<endl; for(int i=0;i<n;i++) visited[i]=false; decide(0); for(int i=0;i<n;i++) cout<<range[i].first<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Integers on a Tree |
User | fiord |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1898 Byte |
Status | AC |
Exec Time | 586 ms |
Memory | 13568 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 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, star_01.txt, star_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
binary_01.txt | AC | 547 ms | 10368 KB |
binary_02.txt | AC | 91 ms | 9728 KB |
hand_01.txt | AC | 5 ms | 2560 KB |
hand_02.txt | AC | 5 ms | 2560 KB |
hand_03.txt | AC | 5 ms | 2560 KB |
kary_01.txt | AC | 85 ms | 6656 KB |
kary_02.txt | AC | 499 ms | 7296 KB |
kary_03.txt | AC | 83 ms | 6656 KB |
line_01.txt | AC | 105 ms | 12800 KB |
line_02.txt | AC | 512 ms | 13568 KB |
line_03.txt | AC | 510 ms | 13568 KB |
line_04.txt | AC | 525 ms | 13568 KB |
line_05.txt | AC | 91 ms | 12800 KB |
line_06.txt | AC | 105 ms | 12800 KB |
random0_01.txt | AC | 122 ms | 6656 KB |
random1_01.txt | AC | 523 ms | 7296 KB |
random1_02.txt | AC | 522 ms | 7296 KB |
random1_03.txt | AC | 528 ms | 7296 KB |
random1_04.txt | AC | 557 ms | 7296 KB |
random1_05.txt | AC | 524 ms | 7296 KB |
random1_06.txt | AC | 519 ms | 7296 KB |
random1_07.txt | AC | 524 ms | 7296 KB |
random1_08.txt | AC | 586 ms | 7296 KB |
random2_01.txt | AC | 90 ms | 6656 KB |
random2_02.txt | AC | 90 ms | 6656 KB |
random2_03.txt | AC | 88 ms | 6656 KB |
random2_04.txt | AC | 93 ms | 6656 KB |
random2_05.txt | AC | 128 ms | 6656 KB |
random2_06.txt | AC | 161 ms | 6656 KB |
random3_01.txt | AC | 97 ms | 6656 KB |
random3_02.txt | AC | 125 ms | 6656 KB |
random4_01.txt | AC | 515 ms | 7296 KB |
random4_02.txt | AC | 518 ms | 7296 KB |
random4_03.txt | AC | 533 ms | 7296 KB |
sample_01.txt | AC | 5 ms | 2560 KB |
sample_02.txt | AC | 5 ms | 2560 KB |
sample_03.txt | AC | 5 ms | 2560 KB |
star_01.txt | AC | 525 ms | 7800 KB |
star_02.txt | AC | 102 ms | 7032 KB |