Submission #2097375


Source Code Expand

#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

int n;
int k;

typedef pair<int,int> P;

vector<P> edges[100001];

int l[100001];
int r[100001];

queue<int> que;

int INF = 1e9;


bool solve()
{
	while(!que.empty())
	{
		int v = que.front();
		que.pop();

		int nl = l[v] - 1;
		int nr = r[v] + 1;

		for(P& p : edges[v])
		{
			if(l[p.first] !=INF && abs(nl - l[p.first]) % 2 == 1)
			{
				return false;
			}
			if(l[p.first] == INF || l[p.first] < nl || nr < r[p.first])
			{
				//update
				if(l[p.first] == INF)
				{
					l[p.first] = nl;
					r[p.first] = nr;
				}
				l[p.first] = max(l[p.first] , nl);
				r[p.first] = min(r[p.first] , nr);

				if(!(l[p.first] <= r[p.first]))
					return false;

				que.push(p.first);
			}
		}
	}	
	return true;

}
int main()
{
	fill(l,l + 100001,INF);
	fill(r,r + 100001,INF);
	cin >> n;

	for(int i = 0;i < n - 1;i++)
	{
		int a,b;
		cin >> a >> b;

		edges[a].push_back(P{b,0});
		edges[b].push_back(P{a,0});
	}

	cin >> k;


	for(int i = 0;i < k;i++)
	{
		int v,p;
		cin >> v >> p;
		que.push(v);
		l[v] = p;
		r[v] = p;
	}
	
	if(!solve())
	{
		cout << "No" << endl;
		return 0;
	}

	cout << "Yes" << endl;

	for(int i = 1;i <= n;i++)
	{
		//cerr << i << "-" << l[i] << ":" << r[i] << endl;
		cout << l[i] << endl;
	}

	return 0;
}

Submission Info

Submission Time
Task E - Integers on a Tree
User niuez
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1472 Byte
Status AC
Exec Time 284 ms
Memory 8192 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 39
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 250 ms 8192 KB
binary_02.txt AC 70 ms 7296 KB
hand_01.txt AC 3 ms 3328 KB
hand_02.txt AC 3 ms 3328 KB
hand_03.txt AC 3 ms 3328 KB
kary_01.txt AC 68 ms 7296 KB
kary_02.txt AC 221 ms 7808 KB
kary_03.txt AC 67 ms 7040 KB
line_01.txt AC 78 ms 6528 KB
line_02.txt AC 221 ms 7168 KB
line_03.txt AC 223 ms 7168 KB
line_04.txt AC 234 ms 7296 KB
line_05.txt AC 67 ms 6528 KB
line_06.txt AC 79 ms 6528 KB
random0_01.txt AC 99 ms 7168 KB
random1_01.txt AC 235 ms 7680 KB
random1_02.txt AC 236 ms 7808 KB
random1_03.txt AC 241 ms 7808 KB
random1_04.txt AC 263 ms 7936 KB
random1_05.txt AC 249 ms 7680 KB
random1_06.txt AC 236 ms 7680 KB
random1_07.txt AC 243 ms 7808 KB
random1_08.txt AC 284 ms 8064 KB
random2_01.txt AC 72 ms 7040 KB
random2_02.txt AC 72 ms 7040 KB
random2_03.txt AC 73 ms 7040 KB
random2_04.txt AC 76 ms 7040 KB
random2_05.txt AC 100 ms 7168 KB
random2_06.txt AC 129 ms 7424 KB
random3_01.txt AC 75 ms 7040 KB
random3_02.txt AC 101 ms 7168 KB
random4_01.txt AC 231 ms 7680 KB
random4_02.txt AC 230 ms 7680 KB
random4_03.txt AC 229 ms 7680 KB
sample_01.txt AC 3 ms 3328 KB
sample_02.txt AC 3 ms 3328 KB
sample_03.txt AC 3 ms 3328 KB
star_01.txt AC 236 ms 8180 KB
star_02.txt AC 81 ms 7540 KB