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
AC × 3
AC × 38
WA × 1
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