Submission #1807199


Source Code Expand

#include <cstdio>
#include <algorithm>

const int N = 2e5 + 5;
inline int Get() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int Num = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9')
		Num = (Num << 3) + (Num << 1) + ch - '0';
	return Num;
}

int n, strA, strB, w[N][2], que[N], qn, vis[N], flag[N], ans;
struct Graph{
	int tot, first[N], next[N << 1], end[N << 1], dist[N], fa[N], sze[N], dfn[N];
	inline void AddEdge(int x, int y) {
		next[++tot] = first[x], first[x] = tot, end[tot] = y;
		next[++tot] = first[y], first[y] = tot, end[tot] = x;
	}
	void Dfs(int x) {
		que[qn = 1] = x, fa[x] = 0, dist[x] = 0;
		for (int ql = 1, u; u = que[ql], ql <= qn; sze[u] = 1, ++ql)
			for (int k = first[u], v; v = end[k], k; k = next[k])
				if (v != fa[u]) fa[v] = u, dist[v] = dist[u] + 1, que[++qn] = v;
		
		for (int qr = qn, u; u = que[qr], qr > 1; --qr) sze[fa[u]] += sze[u];
		
		dfn[x] = 1;
		for (int ql = 1, u, cur; u = que[ql], cur = dfn[u], ql <= qn; ++ql) 
			for (int k = first[u], v; v = end[k], k; k = next[k]) 
				if (v != fa[u]) dfn[v] = cur + 1, cur += sze[v];
	}
	inline bool check(int x, int y) {
		if (dist[x] < dist[y]) std :: swap(x, y);
		if (dist[x] - dist[y] > 2) return true;
		if (dfn[y] <= dfn[x] && dfn[x] < dfn[y] + sze[y]) return false;
		if (fa[x] == fa[y]) return false;
		return true;
	}
}A, B;

int main() {
	n = Get(), strA = Get(), strB = Get();
	for (int i = 1; i < n; ++i) w[i][0] = Get(), w[i][1] = Get();
	for (int i = 1; i < n; ++i) B.AddEdge(Get(), Get());
	
	B.Dfs(strB);
	for (int k = 1; k <= n; ++k)
		if (B.check(w[k][0], w[k][1])) flag[w[k][0]] = flag[w[k][1]] = true;
		else A.AddEdge(w[k][0], w[k][1]);
		
	que[qn = 1] = strA, vis[strA] = true, A.dist[strA] = 0;
	for (int ql = 1, u; u = que[ql], ql <= qn; ++ql) 
		for (int k = A.first[u], v; v = A.end[k], k; k = A.next[k]) 
			if ((A.dist[v] = A.dist[u] + 1) < B.dist[v] && !vis[v]) vis[v] = true, que[++qn] = v;
	
	for (int i = 1; i <= n; ++i) 
		if (vis[i]) {
			ans = std :: max(ans, B.dist[i] * 2);
			if (flag[i]) {
				puts("-1");
				return 0;
			}
		}
		
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User wy1627
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 2186 Byte
Status AC
Exec Time 73 ms
Memory 18176 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 5
AC × 103
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 54 ms 18048 KB
doublestar1 AC 52 ms 17920 KB
doublestar2 AC 52 ms 18048 KB
doublestar3 AC 50 ms 17920 KB
doublestar4 AC 53 ms 18048 KB
doublestar5 AC 54 ms 18176 KB
doublestar6 AC 51 ms 17920 KB
doublestar7 AC 50 ms 17920 KB
example0 AC 3 ms 14464 KB
example1 AC 3 ms 14464 KB
example2 AC 3 ms 14464 KB
example3 AC 3 ms 14464 KB
example4 AC 3 ms 14464 KB
giri0 AC 59 ms 18176 KB
giri1 AC 59 ms 18048 KB
giri2 AC 60 ms 18048 KB
giri3 AC 58 ms 18048 KB
giri4 AC 59 ms 18048 KB
giri5 AC 61 ms 18176 KB
giri6 AC 61 ms 18176 KB
giri7 AC 60 ms 18048 KB
giri8 AC 73 ms 18048 KB
giri9 AC 60 ms 18048 KB
maxrand0 AC 58 ms 18176 KB
maxrand1 AC 59 ms 18048 KB
maxrand2 AC 58 ms 18176 KB
maxrand3 AC 57 ms 18048 KB
maxrand4 AC 55 ms 18048 KB
maxrand5 AC 56 ms 18048 KB
maxrand6 AC 56 ms 18048 KB
maxrand7 AC 57 ms 18048 KB
maxrand8 AC 55 ms 18048 KB
maxrand9 AC 57 ms 18048 KB
narashi0 AC 58 ms 18048 KB
narashi1 AC 58 ms 18048 KB
narashi2 AC 58 ms 18048 KB
narashi3 AC 59 ms 18048 KB
narashi4 AC 60 ms 18048 KB
narashi5 AC 61 ms 18048 KB
narashi6 AC 62 ms 18048 KB
narashi7 AC 61 ms 18176 KB
narashi8 AC 60 ms 18176 KB
narashi9 AC 59 ms 18048 KB
ok0 AC 58 ms 18048 KB
ok1 AC 58 ms 18048 KB
ok2 AC 59 ms 18048 KB
ok3 AC 60 ms 18176 KB
ok4 AC 61 ms 18048 KB
ok5 AC 60 ms 18176 KB
ok6 AC 58 ms 18048 KB
ok7 AC 60 ms 18048 KB
ok8 AC 59 ms 18176 KB
ok9 AC 58 ms 18048 KB
ouh0 AC 53 ms 17920 KB
ouh1 AC 55 ms 18048 KB
ouh2 AC 54 ms 17920 KB
ouh3 AC 57 ms 18048 KB
ouh4 AC 56 ms 18048 KB
ouh5 AC 55 ms 17920 KB
ouh6 AC 57 ms 18048 KB
ouh7 AC 54 ms 17920 KB
ouh8 AC 59 ms 18048 KB
ouh9 AC 58 ms 18048 KB
same0 AC 62 ms 18048 KB
same1 AC 61 ms 18048 KB
same2 AC 60 ms 18176 KB
same3 AC 58 ms 18176 KB
same4 AC 57 ms 18048 KB
same5 AC 62 ms 18048 KB
same6 AC 58 ms 18048 KB
same7 AC 61 ms 18048 KB
same8 AC 55 ms 18048 KB
same9 AC 63 ms 18048 KB
sameline0 AC 58 ms 18048 KB
sameline1 AC 63 ms 18176 KB
sameline2 AC 56 ms 18048 KB
sameline3 AC 58 ms 18048 KB
sameline4 AC 57 ms 18048 KB
sameline5 AC 58 ms 18048 KB
sameline6 AC 55 ms 18048 KB
sameline7 AC 61 ms 18048 KB
sameline8 AC 59 ms 18176 KB
sameline9 AC 58 ms 18176 KB
star0 AC 50 ms 18048 KB
star1 AC 50 ms 18048 KB
star2 AC 47 ms 18048 KB
star3 AC 49 ms 18048 KB
star4 AC 51 ms 18048 KB
star5 AC 53 ms 18048 KB
star6 AC 50 ms 18048 KB
star7 AC 49 ms 18048 KB
star8 AC 49 ms 18048 KB
star9 AC 55 ms 18176 KB
supersmall0 AC 3 ms 14464 KB
supersmall1 AC 3 ms 14464 KB
supersmall2 AC 3 ms 14464 KB
supersmall3 AC 3 ms 14464 KB
supersmall4 AC 3 ms 14464 KB
supersmall5 AC 3 ms 14464 KB
supersmall6 AC 3 ms 14464 KB
supersmall7 AC 3 ms 14464 KB
supersmall8 AC 3 ms 14464 KB
supersmall9 AC 3 ms 14464 KB