Submission #1792035


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 2e5 + 5, M = N * 2 , inf = 1e9 + 7;
using namespace std ;

bool vis[N], path[N] ;
int n, rt, S, e, ter[M], nxt[M], lnk[N], dep[N], fa[N], ans ;
struct edge {
	int x, y ;
} ed[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

void dfs(int p, int las) {
	for (int i = lnk[p] ; i; i = nxt[i]) if (ter[i] != las) {
		dep[ter[i]] = dep[p] + 1 ;
		fa[ter[i]] = p ;
		dfs(ter[i], p) ;
	}
}

void dfs2(int p, int las, int len) {
	if (ans == inf) return ;
	if (dep[p] < len) {
		ans = max(ans, (len - 1) * 2 + 1) ;
		return ;
	}
	if (dep[p] == len) {
		ans = max(ans, len * 2) ;
		return ;
	}
	if (vis[p]) {
		ans = inf ;
		return ;
	}
	bool flg = false ;
	for (int i = lnk[p] ; i; i = nxt[i]) if (ter[i] != las) flg = true, dfs2(ter[i], p, len + 1) ;
	if (!flg) {
		ans = max(ans, dep[p] * 2) ;
		return ;
	}
}

bool chk(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y) ;
	if (fa[x] == y) return false ;
	if (fa[fa[x]] == y) return false ;
	if (fa[x] == fa[y]) return false ;
	return true ;
}

int main() {
	scanf("%d%d%d", &n, &S, &rt) ;
	rep(i, 1, n - 1) scanf("%d%d", &ed[i].x, &ed[i].y) ;
	int x, y ;
	rep(i, 1, n - 1) {
		scanf("%d%d", &x, &y) ;
		add(x, y), add(y, x) ;
	}
	dfs(rt, 0) ;
	rep(i, 1, n - 1) if (chk(ed[i].x, ed[i].y)) vis[ed[i].x] = vis[ed[i].y] = true ;
	rep(i, 1, n) lnk[i] = 0 ;
	rep(i, 1, e) nxt[i] = 0 ; e = 0 ;
	rep(i, 1, n - 1) add(ed[i].x, ed[i].y), add(ed[i].y, ed[i].x) ;
	dfs2(S, 0, 0) ;
	if (ans == (int) (1e9 + 7)) {
		printf("-1\n") ;
	} else printf("%d\n", ans) ;
	return 0 ; 
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User mjy0724
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1797 Byte
Status WA
Exec Time 95 ms
Memory 15872 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:60:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &S, &rt) ;
                               ^
./Main.cpp:61:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n - 1) scanf("%d%d", &ed[i].x, &ed[i].y) ;
                                                     ^
./Main.cpp:64:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y) ;
                         ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 2
WA × 3
AC × 93
WA × 10
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 77 ms 7424 KB
doublestar1 AC 73 ms 7168 KB
doublestar2 AC 74 ms 7296 KB
doublestar3 AC 70 ms 7168 KB
doublestar4 AC 77 ms 7424 KB
doublestar5 AC 77 ms 7424 KB
doublestar6 AC 71 ms 7168 KB
doublestar7 AC 72 ms 7168 KB
example0 AC 2 ms 4352 KB
example1 WA 2 ms 4352 KB
example2 WA 2 ms 4352 KB
example3 AC 2 ms 4352 KB
example4 WA 2 ms 4352 KB
giri0 AC 80 ms 7424 KB
giri1 AC 79 ms 7296 KB
giri2 AC 80 ms 7424 KB
giri3 AC 81 ms 7296 KB
giri4 AC 82 ms 7296 KB
giri5 AC 83 ms 7424 KB
giri6 AC 83 ms 7424 KB
giri7 AC 80 ms 7296 KB
giri8 AC 81 ms 7424 KB
giri9 AC 81 ms 7424 KB
maxrand0 AC 80 ms 7424 KB
maxrand1 AC 79 ms 7424 KB
maxrand2 AC 80 ms 7424 KB
maxrand3 AC 78 ms 7424 KB
maxrand4 AC 76 ms 7296 KB
maxrand5 AC 77 ms 7296 KB
maxrand6 AC 77 ms 7296 KB
maxrand7 AC 80 ms 7424 KB
maxrand8 AC 76 ms 7296 KB
maxrand9 AC 79 ms 7424 KB
narashi0 AC 81 ms 7296 KB
narashi1 AC 80 ms 7296 KB
narashi2 AC 79 ms 7296 KB
narashi3 AC 82 ms 7296 KB
narashi4 AC 85 ms 7424 KB
narashi5 AC 83 ms 7296 KB
narashi6 AC 87 ms 7424 KB
narashi7 AC 82 ms 7424 KB
narashi8 AC 85 ms 7424 KB
narashi9 AC 81 ms 7296 KB
ok0 AC 88 ms 14848 KB
ok1 AC 91 ms 15744 KB
ok2 AC 88 ms 12800 KB
ok3 AC 90 ms 15872 KB
ok4 AC 82 ms 10880 KB
ok5 AC 90 ms 12544 KB
ok6 AC 93 ms 13312 KB
ok7 AC 85 ms 10880 KB
ok8 WA 92 ms 14208 KB
ok9 AC 87 ms 13696 KB
ouh0 AC 77 ms 7936 KB
ouh1 AC 80 ms 8832 KB
ouh2 AC 76 ms 10112 KB
ouh3 AC 80 ms 10240 KB
ouh4 AC 80 ms 9600 KB
ouh5 AC 83 ms 13952 KB
ouh6 WA 85 ms 14848 KB
ouh7 AC 78 ms 9216 KB
ouh8 WA 87 ms 13056 KB
ouh9 AC 86 ms 14848 KB
same0 AC 82 ms 7168 KB
same1 AC 84 ms 7168 KB
same2 AC 81 ms 7296 KB
same3 AC 81 ms 7296 KB
same4 AC 79 ms 7168 KB
same5 AC 82 ms 7168 KB
same6 AC 79 ms 7168 KB
same7 AC 83 ms 7168 KB
same8 AC 76 ms 7168 KB
same9 AC 85 ms 7296 KB
sameline0 AC 88 ms 15232 KB
sameline1 AC 95 ms 15360 KB
sameline2 AC 87 ms 13184 KB
sameline3 AC 88 ms 14208 KB
sameline4 AC 89 ms 14976 KB
sameline5 AC 90 ms 14848 KB
sameline6 AC 87 ms 12160 KB
sameline7 AC 94 ms 14592 KB
sameline8 AC 92 ms 13312 KB
sameline9 AC 89 ms 12160 KB
star0 AC 73 ms 7168 KB
star1 AC 72 ms 7168 KB
star2 AC 71 ms 7168 KB
star3 AC 72 ms 7168 KB
star4 AC 75 ms 7168 KB
star5 AC 76 ms 7168 KB
star6 AC 74 ms 7168 KB
star7 AC 74 ms 7168 KB
star8 AC 73 ms 7168 KB
star9 AC 75 ms 7296 KB
supersmall0 AC 2 ms 4352 KB
supersmall1 AC 2 ms 4352 KB
supersmall2 AC 2 ms 4352 KB
supersmall3 WA 2 ms 4352 KB
supersmall4 AC 2 ms 4352 KB
supersmall5 WA 2 ms 4352 KB
supersmall6 AC 2 ms 4352 KB
supersmall7 AC 2 ms 4352 KB
supersmall8 WA 2 ms 4352 KB
supersmall9 WA 2 ms 4352 KB