AtCoder Grand Contest 005

Submission #1355530

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
typedef pair<int,int> pii;
int n, x, y, dep[200005], par[20][200005];
int da[200005], db[200005];

vector<int> ra[200005], rb[200005];
vector<pii> red;

queue<int> q;

void calc (int cur, int prv) {
	dep[cur] = dep[prv] + 1;
	par[0][cur] = prv;
	for(auto &nxt : rb[cur]) {
		if(nxt == prv) continue;
		calc(nxt, cur);
	}
}

int getdist (int A, int B) {
	if(dep[A] < dep[B]) swap(A, B);
	int ret = 0;
	for(int i=20;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A]; ret += (1<<i);
		}
	}
	if(A == B) return ret;
	for(int i=20;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
			ret += (1<<i) * 2;
		}
	}
	return ret + 2;
}

int main() {
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		red.push_back({A, B});
		ra[A].push_back(B);
		ra[B].push_back(A);
	}
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		rb[A].push_back(B);
		rb[B].push_back(A);
	}
	calc(1, 0);
	for(int k=1;k<20;k++) {
		for(int i=1;i<=n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
	for(int i=1;i<=n;i++) {da[i] = inf; db[i] = inf;}
	db[y] = 2; q.push(y);
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(auto &nxt : rb[cur]) {
			if(db[nxt] == inf) {
				db[nxt] = db[cur] + 2;
				q.push(nxt);
			}
		}
	}
	da[x] = 1; q.push(x);
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(auto &nxt : ra[cur]) {
			if(da[nxt] == inf && db[nxt] > da[cur] + 3) {
				da[nxt] = da[cur] + 2;
				q.push(nxt);
			}
		}
	}
	for(auto &T : red) {
		int A = T.first, B = T.second;
		if(getdist(A, B) >= 3 && (da[A] != inf || da[B] != inf)) {
			puts("-1"); return 0;
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++) {
		if(da[i] != inf) ans = max(ans, db[i]);
	}
 	printf("%d\n",ans-2);
}



Submission

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

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:26: 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:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A,&B);
^
./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&A,&B);
^

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 166 ms 42352 KB
doublestar1 AC 157 ms 41712 KB
doublestar2 AC 167 ms 42224 KB
doublestar3 AC 144 ms 41456 KB
doublestar4 AC 159 ms 42736 KB
doublestar5 AC 172 ms 42736 KB
doublestar6 AC 156 ms 41584 KB
doublestar7 AC 166 ms 41584 KB
example0 AC 8 ms 26880 KB
example1 AC 8 ms 26880 KB
example2 AC 8 ms 26880 KB
example3 AC 8 ms 26880 KB
example4 AC 8 ms 26880 KB
giri0 AC 173 ms 42608 KB
giri1 AC 183 ms 41456 KB
giri2 AC 173 ms 41712 KB
giri3 AC 185 ms 41584 KB
giri4 AC 191 ms 41456 KB
giri5 AC 196 ms 42096 KB
giri6 AC 192 ms 41968 KB
giri7 AC 180 ms 41840 KB
giri8 AC 190 ms 41712 KB
giri9 AC 184 ms 41968 KB
maxrand0 AC 178 ms 42096 KB
maxrand1 AC 183 ms 41968 KB
maxrand2 AC 174 ms 42096 KB
maxrand3 AC 170 ms 41840 KB
maxrand4 AC 176 ms 41584 KB
maxrand5 AC 173 ms 41584 KB
maxrand6 AC 166 ms 41584 KB
maxrand7 AC 187 ms 41968 KB
maxrand8 AC 179 ms 41456 KB
maxrand9 AC 166 ms 41840 KB
narashi0 AC 185 ms 41200 KB
narashi1 AC 187 ms 41328 KB
narashi2 AC 181 ms 41456 KB
narashi3 AC 189 ms 41712 KB
narashi4 AC 196 ms 41712 KB
narashi5 AC 179 ms 41840 KB
narashi6 AC 210 ms 41456 KB
narashi7 AC 188 ms 42096 KB
narashi8 AC 203 ms 41840 KB
narashi9 AC 187 ms 41456 KB
ok0 AC 226 ms 47472 KB
ok1 AC 212 ms 49008 KB
ok2 AC 220 ms 45168 KB
ok3 AC 215 ms 46320 KB
ok4 AC 187 ms 44016 KB
ok5 AC 229 ms 45296 KB
ok6 AC 203 ms 45808 KB
ok7 AC 190 ms 44272 KB
ok8 AC 236 ms 46576 KB
ok9 AC 209 ms 45680 KB
ouh0 AC 152 ms 42992 KB
ouh1 AC 179 ms 43760 KB
ouh2 AC 188 ms 43120 KB
ouh3 AC 203 ms 44528 KB
ouh4 AC 201 ms 43888 KB
ouh5 AC 189 ms 44784 KB
ouh6 AC 224 ms 46576 KB
ouh7 AC 183 ms 42992 KB
ouh8 AC 214 ms 44528 KB
ouh9 AC 209 ms 46192 KB
same0 AC 191 ms 41840 KB
same1 AC 189 ms 41712 KB
same2 AC 186 ms 42096 KB
same3 AC 191 ms 42096 KB
same4 AC 185 ms 41584 KB
same5 AC 183 ms 41584 KB
same6 AC 180 ms 41840 KB
same7 AC 181 ms 41584 KB
same8 AC 197 ms 41456 KB
same9 AC 197 ms 42096 KB
sameline0 AC 201 ms 48624 KB
sameline1 AC 214 ms 49520 KB
sameline2 AC 206 ms 50032 KB
sameline3 AC 196 ms 47088 KB
sameline4 AC 215 ms 48112 KB
sameline5 AC 207 ms 48112 KB
sameline6 AC 189 ms 46704 KB
sameline7 AC 206 ms 49136 KB
sameline8 AC 206 ms 48624 KB
sameline9 AC 208 ms 50672 KB
star0 AC 150 ms 43504 KB
star1 AC 132 ms 43376 KB
star2 AC 130 ms 43504 KB
star3 AC 146 ms 43376 KB
star4 AC 147 ms 43504 KB
star5 AC 153 ms 43760 KB
star6 AC 134 ms 43632 KB
star7 AC 146 ms 43376 KB
star8 AC 148 ms 43376 KB
star9 AC 153 ms 43888 KB
supersmall0 AC 8 ms 26880 KB
supersmall1 AC 8 ms 26880 KB
supersmall2 AC 8 ms 26880 KB
supersmall3 AC 8 ms 26880 KB
supersmall4 AC 8 ms 26880 KB
supersmall5 AC 8 ms 26880 KB
supersmall6 AC 8 ms 26880 KB
supersmall7 AC 8 ms 26880 KB
supersmall8 AC 8 ms 26880 KB
supersmall9 AC 8 ms 26880 KB