Submission #1697377


Source Code Expand

//2017-10-21
//miaomiao
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define pb push_back
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define Forr(i, a, b) for(int i = (a); i >= (int)(b); --i)

#define LOG 20
#define N (200000+5)

vector<int> G1[N], G2[N];

int n, ans, dep2[N], u1[N], v1[N], f[N][LOG];
bool reach[N];

void Dfs2(int now, int D, int F){
	dep2[now] = D; f[now][0] = F;
	For(i, 1, 18) f[now][i] = f[f[now][i-1]][i-1];

	For(i, 0, G2[now].size()-1)
		if(G2[now][i] != F) Dfs2(G2[now][i], D+1, now);
}

void Dfs1(int now, int D, int F){
	if(dep2[now] <= D) return;
	
	reach[now] = true; ans = max(ans, dep2[now]);
	For(i, 0, G1[now].size()-1)
		if(G1[now][i] != F) Dfs1(G1[now][i], D+1, now);
}

int Dis(int u, int v){
	if(dep2[u] < dep2[v]) swap(u, v);

	int ret = 0;
	Forr(i, 18, 0) if(dep2[f[u][i]] >= dep2[v]){
		ret += 1<<i; u = f[u][i];
	}
	if(u == v) return ret;
	
	Forr(i, 18, 0) if(f[u][i] ^ f[v][i]){
		ret += (1<<i) << 1;
		u = f[u][i]; v = f[v][i];
	}
	return ret + 2;
}

void Check(){
	int u, v;

	For(i, 1, n) ++dep2[i];
	For(i, 1, n-1){
		u = u1[i], v = v1[i];
      	if(Dis(u, v) >= 3){puts("-1"); return;}
		if(!reach[u] || !reach[v]) continue;
	}

	printf("%d\n", ans<<1);
}

int main(){
	int st1, st2, u, v;

	scanf("%d%d%d", &n, &st1, &st2);
	
	For(i, 1, n-1){
		scanf("%d%d", &u, &v);
		G1[u].pb(v); G1[v].pb(u);
		u1[i] = u; v1[i] = v;
	}
	For(i, 1, n-1){
		scanf("%d%d", &u, &v);
		G2[u].pb(v); G2[v].pb(u);
	}

	Dfs2(st2, 0, 0); Dfs1(st1, 0, 0);
	Check();

	return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User miaomiao
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1722 Byte
Status WA
Exec Time 251 ms
Memory 54524 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &st1, &st2);
                                 ^
./Main.cpp:77:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
                        ^
./Main.cpp:82:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 4
WA × 1
AC × 77
WA × 26
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All 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
Case Name Status Exec Time Memory
doublestar0 AC 163 ms 40696 KB
doublestar1 AC 146 ms 40056 KB
doublestar2 AC 164 ms 40440 KB
doublestar3 AC 148 ms 39928 KB
doublestar4 AC 158 ms 40952 KB
doublestar5 AC 168 ms 40952 KB
doublestar6 AC 160 ms 39928 KB
doublestar7 AC 145 ms 40056 KB
example0 AC 5 ms 13440 KB
example1 AC 5 ms 13440 KB
example2 WA 5 ms 13440 KB
example3 AC 5 ms 13440 KB
example4 AC 5 ms 13440 KB
giri0 AC 176 ms 41344 KB
giri1 WA 175 ms 40192 KB
giri2 AC 183 ms 40320 KB
giri3 WA 178 ms 40320 KB
giri4 WA 184 ms 40192 KB
giri5 WA 198 ms 40704 KB
giri6 WA 185 ms 40704 KB
giri7 WA 178 ms 40448 KB
giri8 AC 192 ms 40448 KB
giri9 AC 183 ms 40704 KB
maxrand0 AC 174 ms 40704 KB
maxrand1 AC 190 ms 40576 KB
maxrand2 AC 180 ms 40704 KB
maxrand3 AC 172 ms 40320 KB
maxrand4 AC 173 ms 40192 KB
maxrand5 AC 175 ms 40192 KB
maxrand6 AC 166 ms 40192 KB
maxrand7 AC 172 ms 40448 KB
maxrand8 AC 169 ms 40064 KB
maxrand9 AC 174 ms 40448 KB
narashi0 WA 175 ms 39936 KB
narashi1 WA 176 ms 40064 KB
narashi2 WA 171 ms 40192 KB
narashi3 WA 178 ms 40448 KB
narashi4 WA 185 ms 40320 KB
narashi5 WA 176 ms 40576 KB
narashi6 WA 188 ms 40192 KB
narashi7 WA 189 ms 40704 KB
narashi8 WA 182 ms 40448 KB
narashi9 WA 175 ms 40192 KB
ok0 AC 224 ms 52476 KB
ok1 AC 209 ms 54140 KB
ok2 WA 200 ms 49148 KB
ok3 AC 207 ms 54524 KB
ok4 AC 197 ms 45952 KB
ok5 AC 206 ms 48764 KB
ok6 AC 203 ms 49916 KB
ok7 AC 194 ms 45824 KB
ok8 WA 209 ms 51708 KB
ok9 AC 202 ms 50428 KB
ouh0 WA 155 ms 42368 KB
ouh1 AC 194 ms 43648 KB
ouh2 WA 169 ms 44672 KB
ouh3 AC 182 ms 45440 KB
ouh4 WA 191 ms 44544 KB
ouh5 AC 190 ms 50684 KB
ouh6 WA 196 ms 52476 KB
ouh7 AC 180 ms 43776 KB
ouh8 WA 199 ms 49788 KB
ouh9 AC 198 ms 52476 KB
same0 AC 199 ms 40448 KB
same1 AC 196 ms 40320 KB
same2 AC 185 ms 40704 KB
same3 AC 193 ms 40576 KB
same4 AC 184 ms 40192 KB
same5 AC 211 ms 40192 KB
same6 AC 197 ms 40448 KB
same7 AC 208 ms 40192 KB
same8 AC 194 ms 40064 KB
same9 AC 222 ms 40576 KB
sameline0 AC 239 ms 53120 KB
sameline1 AC 251 ms 53632 KB
sameline2 AC 228 ms 49920 KB
sameline3 AC 231 ms 51584 KB
sameline4 AC 235 ms 52992 KB
sameline5 AC 240 ms 52736 KB
sameline6 AC 230 ms 48256 KB
sameline7 AC 246 ms 52224 KB
sameline8 AC 238 ms 50432 KB
sameline9 AC 237 ms 48384 KB
star0 AC 150 ms 41204 KB
star1 AC 133 ms 41332 KB
star2 AC 130 ms 41204 KB
star3 AC 146 ms 41076 KB
star4 AC 146 ms 41204 KB
star5 AC 154 ms 41588 KB
star6 AC 135 ms 41332 KB
star7 AC 138 ms 41204 KB
star8 AC 136 ms 41076 KB
star9 AC 149 ms 41716 KB
supersmall0 AC 5 ms 13440 KB
supersmall1 AC 5 ms 13440 KB
supersmall2 AC 5 ms 13440 KB
supersmall3 WA 5 ms 13440 KB
supersmall4 AC 5 ms 13440 KB
supersmall5 AC 5 ms 13440 KB
supersmall6 AC 5 ms 13440 KB
supersmall7 WA 5 ms 13440 KB
supersmall8 AC 5 ms 13440 KB
supersmall9 AC 5 ms 13440 KB