Submission #1226570
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
#define inf 1e9
ll n,k;
vector<P> g[111111];
ll dist[111111];
ll vn[111111];
int main(){
cin.sync_with_stdio(false);
cin>>n;
rep(i,n-1){
int a,b;
cin>>a>>b;
g[a].pb(P(b,1)); g[b].pb(P(a,1));
}
cin>>k;
memset(vn,-1,sizeof(vn));
rep(i,k){
int v,p;
cin>>v>>p;
g[0].pb(P(v,p));
vn[v]=p;
}
rep(i,111111)dist[i]=inf;
priority_queue<P,vector<P>,greater<P> > q;
q.push(P(0,0));
while(q.size()){
ll nd=q.top().fi,nv=q.top().se;
q.pop();
if(dist[nv]!=inf)continue;
dist[nv]=nd;
for(P np:g[nv]){
q.push(P(np.se+nd,np.fi));
}
}
bool ok=true;
repl(i,1,n+1){
if(vn[i]!=-1&&vn[i]!=dist[i])ok=false;
}
if(ok){
cout<<"Yes"<<endl;
repl(i,1,n+1){
cout<<dist[i]<<endl;
}
}else cout<<"No"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Integers on a Tree |
User |
yamad |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1420 Byte |
Status |
WA |
Exec Time |
264 ms |
Memory |
16496 KB |
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 |
AC |
223 ms |
12276 KB |
binary_02.txt |
AC |
48 ms |
10240 KB |
hand_01.txt |
AC |
3 ms |
4608 KB |
hand_02.txt |
AC |
3 ms |
4608 KB |
hand_03.txt |
AC |
3 ms |
4608 KB |
kary_01.txt |
AC |
52 ms |
11260 KB |
kary_02.txt |
AC |
205 ms |
10628 KB |
kary_03.txt |
AC |
52 ms |
9992 KB |
line_01.txt |
AC |
63 ms |
10364 KB |
line_02.txt |
AC |
186 ms |
9984 KB |
line_03.txt |
AC |
187 ms |
9984 KB |
line_04.txt |
AC |
217 ms |
10748 KB |
line_05.txt |
AC |
34 ms |
9344 KB |
line_06.txt |
AC |
62 ms |
10364 KB |
random0_01.txt |
AC |
88 ms |
12020 KB |
random1_01.txt |
AC |
222 ms |
10760 KB |
random1_02.txt |
AC |
221 ms |
10876 KB |
random1_03.txt |
AC |
225 ms |
11004 KB |
random1_04.txt |
AC |
246 ms |
12148 KB |
random1_05.txt |
AC |
225 ms |
10496 KB |
random1_06.txt |
AC |
222 ms |
10496 KB |
random1_07.txt |
AC |
220 ms |
10752 KB |
random1_08.txt |
AC |
264 ms |
14448 KB |
random2_01.txt |
AC |
63 ms |
9984 KB |
random2_02.txt |
AC |
66 ms |
9856 KB |
random2_03.txt |
AC |
65 ms |
10112 KB |
random2_04.txt |
AC |
62 ms |
9984 KB |
random2_05.txt |
AC |
88 ms |
12020 KB |
random2_06.txt |
AC |
108 ms |
14448 KB |
random3_01.txt |
AC |
66 ms |
9984 KB |
random3_02.txt |
WA |
249 ms |
12148 KB |
random4_01.txt |
AC |
215 ms |
10496 KB |
random4_02.txt |
AC |
221 ms |
10624 KB |
random4_03.txt |
AC |
219 ms |
10752 KB |
sample_01.txt |
AC |
3 ms |
4608 KB |
sample_02.txt |
AC |
3 ms |
4608 KB |
sample_03.txt |
AC |
3 ms |
4608 KB |
star_01.txt |
AC |
215 ms |
16496 KB |
star_02.txt |
AC |
58 ms |
16496 KB |