AtCoder Regular Contest 063

Submission #972322

Source codeソースコード

#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

Task問題 E - 木と整数 / Integers on a Tree
User nameユーザ名 fiord
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1898 Byte
File nameファイル名
Exec time実行時間 586 ms
Memory usageメモリ使用量 13568 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample_01.txt,sample_02.txt,sample_03.txt
All 800 / 800 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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