AtCoder Grand Contest 005

Submission #1356091

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9;
int n, x, y, rp[200010], rd[200010], bp[200010], bd[200010], ans;
vector<int> re[200010], be[200010];

void T_T(){ puts("-1"); exit(0); }

void f(int t, int x, int pr, int de, int *p, int *d){
	if(!t && bd[x] <= de) return;
	d[x] = de;
	p[x] = pr;
	if(t){
		for(auto &i : be[x]){
			if(i != pr) f(t, i, x, de + 1, p, d);
		}
	}
	else{
		for(auto &i : re[x]){
			if(i != pr) f(t, i, x, de + 1, p, d);
		}
	}
}

int main(){
	scanf("%d%d%d", &n, &x, &y);
	auto in = [](int t){
		for(int i = 0, x, y; i < n - 1; i++){
			scanf("%d%d", &x, &y);
			(t ? be[x] : re[x]).push_back(y);
			(t ? be[y] : re[y]).push_back(x);
		}
	};
	in(0); in(1);
	f(1, y, 0, 0, bp, bd);
	fill(rd + 1, rd + n + 1, inf);
	f(0, x, 0, 0, rp, rd);
	for(int i = 1; i <= n; i++){
		for(auto &j : re[i]){
			int a = i, b = j;
			if(bd[a] > bd[b]) swap(a, b);
			if(bp[b] == a || bp[bp[b]] == a || bp[a] == bp[b]) continue;
			if(bd[a] > rd[a] || bd[b] > rd[b]) T_T();
		}
	}
	for(int i = 1; i <= n; i++) if(rd[i] < inf) ans = max(ans, 2 * bd[i]);
	printf("%d\n", ans);
}

Submission

Task問題 E - Sugigma: The Showdown
User nameユーザ名 Donghyun Kim
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1400
Source lengthソースコード長 1152 Byte
File nameファイル名
Exec time実行時間 205 ms
Memory usageメモリ使用量 39420 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:27:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &x, &y);
^
./Main.cpp: In lambda function:
./Main.cpp:30:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2,example3,example4
All 1400 / 1400 doublestar0,doublestar1,doublestar2,doublestar3,doublestar4,doublestar5,doublestar6,doublestar7,example0,example1,example2,example3,example4,giri0,giri1,giri2,giri3,giri4,giri5,giri6,giri7,giri8,giri9,maxrand0,maxrand1,maxrand2,maxrand3,maxrand4,maxrand5,maxrand6,maxrand7,maxrand8,maxrand9,narashi0,narashi1,narashi2,narashi3,narashi4,narashi5,narashi6,narashi7,narashi8,narashi9,ok0,ok1,ok2,ok3,ok4,ok5,ok6,ok7,ok8,ok9,ouh0,ouh1,ouh2,ouh3,ouh4,ouh5,ouh6,ouh7,ouh8,ouh9,same0,same1,same2,same3,same4,same5,same6,same7,same8,same9,sameline0,sameline1,sameline2,sameline3,sameline4,sameline5,sameline6,sameline7,sameline8,sameline9,star0,star1,star2,star3,star4,star5,star6,star7,star8,star9,supersmall0,supersmall1,supersmall2,supersmall3,supersmall4,supersmall5,supersmall6,supersmall7,supersmall8,supersmall9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
doublestar0 AC 146 ms 25716 KB
doublestar1 AC 131 ms 24952 KB
doublestar2 AC 136 ms 25464 KB
doublestar3 AC 149 ms 24824 KB
doublestar4 AC 147 ms 25848 KB
doublestar5 AC 144 ms 25976 KB
doublestar6 AC 135 ms 24824 KB
doublestar7 AC 132 ms 24952 KB
example0 AC 6 ms 12544 KB
example1 AC 6 ms 12544 KB
example2 AC 6 ms 12544 KB
example3 AC 6 ms 12544 KB
example4 AC 6 ms 12544 KB
giri0 AC 160 ms 26240 KB
giri1 AC 169 ms 25216 KB
giri2 AC 172 ms 25344 KB
giri3 AC 163 ms 25216 KB
giri4 AC 178 ms 25088 KB
giri5 AC 179 ms 25600 KB
giri6 AC 173 ms 25600 KB
giri7 AC 165 ms 25472 KB
giri8 AC 171 ms 25344 KB
giri9 AC 165 ms 25600 KB
maxrand0 AC 154 ms 25600 KB
maxrand1 AC 167 ms 25472 KB
maxrand2 AC 174 ms 25728 KB
maxrand3 AC 149 ms 25344 KB
maxrand4 AC 166 ms 25088 KB
maxrand5 AC 155 ms 25088 KB
maxrand6 AC 147 ms 25088 KB
maxrand7 AC 162 ms 25472 KB
maxrand8 AC 149 ms 25088 KB
maxrand9 AC 151 ms 25472 KB
narashi0 AC 170 ms 24832 KB
narashi1 AC 164 ms 24960 KB
narashi2 AC 159 ms 25088 KB
narashi3 AC 162 ms 25344 KB
narashi4 AC 171 ms 25344 KB
narashi5 AC 165 ms 25472 KB
narashi6 AC 182 ms 25216 KB
narashi7 AC 168 ms 25728 KB
narashi8 AC 176 ms 25472 KB
narashi9 AC 163 ms 25088 KB
ok0 AC 183 ms 37372 KB
ok1 AC 193 ms 39164 KB
ok2 AC 194 ms 34044 KB
ok3 AC 201 ms 39420 KB
ok4 AC 178 ms 30848 KB
ok5 AC 185 ms 33788 KB
ok6 AC 184 ms 34940 KB
ok7 AC 182 ms 30768 KB
ok8 AC 192 ms 36604 KB
ok9 AC 192 ms 35324 KB
ouh0 AC 144 ms 27264 KB
ouh1 AC 164 ms 28544 KB
ouh2 AC 154 ms 29568 KB
ouh3 AC 171 ms 30336 KB
ouh4 AC 178 ms 29440 KB
ouh5 AC 184 ms 35708 KB
ouh6 AC 186 ms 37372 KB
ouh7 AC 180 ms 28800 KB
ouh8 AC 178 ms 34684 KB
ouh9 AC 181 ms 37500 KB
same0 AC 178 ms 25344 KB
same1 AC 170 ms 25216 KB
same2 AC 167 ms 25600 KB
same3 AC 167 ms 25600 KB
same4 AC 156 ms 25088 KB
same5 AC 167 ms 25088 KB
same6 AC 168 ms 25344 KB
same7 AC 169 ms 25088 KB
same8 AC 152 ms 25088 KB
same9 AC 182 ms 25600 KB
sameline0 AC 201 ms 38144 KB
sameline1 AC 202 ms 38656 KB
sameline2 AC 180 ms 34816 KB
sameline3 AC 186 ms 36480 KB
sameline4 AC 182 ms 37888 KB
sameline5 AC 193 ms 37760 KB
sameline6 AC 179 ms 33152 KB
sameline7 AC 196 ms 37248 KB
sameline8 AC 185 ms 35328 KB
sameline9 AC 205 ms 33408 KB
star0 AC 117 ms 26100 KB
star1 AC 109 ms 26228 KB
star2 AC 108 ms 26100 KB
star3 AC 115 ms 25972 KB
star4 AC 116 ms 26100 KB
star5 AC 121 ms 26484 KB
star6 AC 109 ms 26228 KB
star7 AC 114 ms 26100 KB
star8 AC 115 ms 26100 KB
star9 AC 124 ms 26740 KB
supersmall0 AC 6 ms 12544 KB
supersmall1 AC 6 ms 12544 KB
supersmall2 AC 6 ms 12544 KB
supersmall3 AC 6 ms 12544 KB
supersmall4 AC 6 ms 12544 KB
supersmall5 AC 6 ms 12544 KB
supersmall6 AC 6 ms 12544 KB
supersmall7 AC 6 ms 12544 KB
supersmall8 AC 6 ms 12544 KB
supersmall9 AC 6 ms 12544 KB