Submission #1692651
Source Code Expand
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int t[110000];
vector<int>g[110000];
int ijk[110000];
int v[110000];
int main(){
int a;scanf("%d",&a);
for(int i=0;i<a-1;i++){
int p,q;scanf("%d%d",&p,&q);
p--;q--;
g[p].push_back(q);g[q].push_back(p);
}
int b;scanf("%d",&b);
for(int i=0;i<a;i++)t[i]=-1;
for(int i=0;i<a;i++)ijk[i]=mod;
priority_queue<pair<int,int> > Q;
for(int i=0;i<b;i++){
int p,q;scanf("%d%d",&p,&q);p--;
t[p]=q;
ijk[p]=q;
Q.push(make_pair(-q,p));
}
while(Q.size()){
int cost=-Q.top().first;
int at=Q.top().second;
Q.pop();
if(v[at])continue;
v[at]=1;
for(int i=0;i<g[at].size();i++){
int to=g[at][i];
if(v[to]||ijk[to]<=cost+1)continue;
ijk[to]=cost+1;
Q.push(make_pair(-ijk[to],to));
}
}
for(int i=0;i<a;i++){
if(t[i]!=-1&&ijk[i]!=t[i]){
printf("No\n");return 0;
}
for(int j=0;j<g[i].size();j++){
if(ABS(ijk[i]-ijk[g[i][j]])!=1){
printf("No\n");return 0;
}
}
}
printf("Yes\n");
for(int i=0;i<a;i++)printf("%d\n",ijk[i]);
}
Submission Info
Submission Time
2017-10-18 23:14:11+0900
Task
E - Integers on a Tree
User
tozangezan
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1487 Byte
Status
AC
Exec Time
91 ms
Memory
8948 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a;scanf("%d",&a);
^
./Main.cpp:28:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int p,q;scanf("%d%d",&p,&q);
^
./Main.cpp:32:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int b;scanf("%d",&b);
^
./Main.cpp:37:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int p,q;scanf("%d%d",&p,&q);p--;
^
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, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt
Case Name
Status
Exec Time
Memory
binary_01.txt
AC
63 ms
8312 KB
binary_02.txt
AC
41 ms
7168 KB
hand_01.txt
AC
3 ms
2816 KB
hand_02.txt
AC
3 ms
2816 KB
hand_03.txt
AC
3 ms
2816 KB
kary_01.txt
AC
43 ms
7676 KB
kary_02.txt
AC
49 ms
8060 KB
kary_03.txt
AC
41 ms
7552 KB
line_01.txt
AC
52 ms
7420 KB
line_02.txt
AC
43 ms
7808 KB
line_03.txt
AC
43 ms
7808 KB
line_04.txt
AC
61 ms
8060 KB
line_05.txt
AC
34 ms
7168 KB
line_06.txt
AC
51 ms
7420 KB
random0_01.txt
AC
77 ms
7676 KB
random1_01.txt
AC
63 ms
7936 KB
random1_02.txt
AC
65 ms
7936 KB
random1_03.txt
AC
69 ms
8064 KB
random1_04.txt
AC
82 ms
8316 KB
random1_05.txt
AC
63 ms
7936 KB
random1_06.txt
AC
64 ms
7936 KB
random1_07.txt
AC
70 ms
7936 KB
random1_08.txt
AC
91 ms
8696 KB
random2_01.txt
AC
53 ms
7168 KB
random2_02.txt
AC
51 ms
7168 KB
random2_03.txt
AC
55 ms
7296 KB
random2_04.txt
AC
56 ms
7296 KB
random2_05.txt
AC
72 ms
7676 KB
random2_06.txt
AC
80 ms
8056 KB
random3_01.txt
AC
52 ms
7168 KB
random3_02.txt
AC
70 ms
7676 KB
random4_01.txt
AC
60 ms
7936 KB
random4_02.txt
AC
62 ms
7936 KB
random4_03.txt
AC
63 ms
7936 KB
sample_01.txt
AC
3 ms
2816 KB
sample_02.txt
AC
3 ms
2816 KB
sample_03.txt
AC
3 ms
2816 KB
star_01.txt
AC
57 ms
8948 KB
star_02.txt
AC
47 ms
8696 KB