Submission #1689665


Source Code Expand

#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif

#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;

typedef pair<int, int> pii;

typedef long long LL;

template<typename T> inline bool chkmax(T &x, const T &y) {
	return x < y && (~x) ? x = y, 1 : 0;
}

template<typename T> inline bool chkmin(T &x, const T &y) {
	return x > y ? x = y, 1 : 0;
}

#ifdef DEBUG
char *input_file, *output_file;
#endif

struct IO {
	static const int maxn = (1 << 25) + 10;

	char a[maxn], *s, b[maxn], *t;

	void INPUT() {
		s = a;
		t = b;
		#ifdef DEBUG
		FILE *f = fopen(input_file, "r");
		a[fread(a, 1, sizeof a, f)] = 0;
		#else
		a[fread(a, 1, sizeof a, stdin)] = 0;
		#endif
	}

	void OUTPUT() {
#ifdef DEBUG
		FILE *f = fopen(output_file, "w");
		fwrite(b, 1, t - b, f);
#else
		fwrite(b, 1, t - b, stdout);
#endif
	}

	operator int() {
		int x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator LL() {
		LL x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator char() {
		while(*s <= 32) {
			++s;
		}
		char ret = *s;
		++s;
		return ret;
	}

	inline void out(int x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(int x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(LL x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(LL x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(char c) {
		*t++ = c;
		return;
	}

	inline void out(char *s) {
		while(*s >= ' ') {
			*t++ = *s++;
		}
		return;
	}
}io;

void Main();

int main(int argc, char *argv[]) {
#ifdef DEBUG
	input_file = argv[1];
	output_file = argv[2];
#endif
	io.INPUT();
	Main();
	io.OUTPUT();
	return 0;
}

//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------

const int maxn = 2e5 + 100;

const int lgn = 19;

int n, r1, r2, ans;
vi g1[maxn], g2[maxn];
int par1[maxn][lgn], par2[maxn][lgn];
int dep1[maxn], dep2[maxn];

void dfs1(int u = r1, int p = 0) {
	par1[u][0] = p;
	forn(i, 1, lgn - 1) {
		par1[u][i] = par1[par1[u][i - 1]][i - 1];
	}
	dep1[u] = dep1[p] + 1;
	for (int v: g1[u]) {
		if(v != p) {
			dfs1(v, u);
		}
	}
	return;
}

void dfs2(int u = r2, int p = 0) {
	par2[u][0] = p;
	forn(i, 1, lgn - 1) {
		par2[u][i] = par2[par2[u][i - 1]][i - 1];
	}
	dep2[u] = dep2[p] + 1;
	for (int v: g2[u]) {
		if(v != p) {
			dfs2(v, u);
		}
	}
	return;
}

int lca(int u, int v) {
	if(dep2[u] < dep2[v]) {
		swap(u, v);
	}
	int dlt = dep2[u] - dep2[v];
	rep(i, lgn) {
		if((dlt >> i) & 1) {
			u = par2[u][i];
		}
	}
	if(u == v) {
		return u;
	}
	per(i, lgn) {
		if(par2[u][i] != par2[v][i]) {
			u = par2[u][i], v = par2[v][i];
		}
	}
	return par2[u][0];
}

void dfs3(int u = r1, int p = 0) {
	debug("dfs3(%d, %d)\n", u, p);
	chkmax(ans, max(dep1[u], dep2[u]) - 1 << 1);
	if(dep1[u] >= dep2[u]) {
		return;
	}
	if(p) {
		int f = lca(u, p);
		if(dep2[u] + dep2[p] - dep2[f] * 2 > 2) {
			ans = -1;
			return;
		}
	}
	for (int v: g1[u]) {
		if(v != p) {
			dfs3(v, u);
		}
	}
	return;
}

void Main() {
	n = io;
	r1 = io;
	r2 = io;
	rep(i, n - 1) {
		int u = io, v = io;
		g1[u].pb(v);
		g1[v].pb(u);
	}
	rep(i, n - 1) {
		int u = io, v = io;
		g2[u].pb(v);
		g2[v].pb(u);
	}
	dfs1();
	dfs2();
	dfs3();
	io.out(ans, '\n');
	return;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User OMTWOCZWEIXVI
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5690 Byte
Status WA
Exec Time 283 ms
Memory 70524 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 5
AC × 86
WA × 17
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 178 ms 62200 KB
doublestar1 AC 162 ms 61560 KB
doublestar2 AC 194 ms 62072 KB
doublestar3 AC 174 ms 61432 KB
doublestar4 AC 175 ms 62456 KB
doublestar5 AC 200 ms 62584 KB
doublestar6 AC 174 ms 61432 KB
doublestar7 AC 164 ms 61560 KB
example0 AC 6 ms 14592 KB
example1 AC 7 ms 14592 KB
example2 AC 6 ms 14592 KB
example3 AC 6 ms 14592 KB
example4 AC 6 ms 14592 KB
giri0 WA 201 ms 62848 KB
giri1 AC 201 ms 61824 KB
giri2 WA 221 ms 61952 KB
giri3 AC 205 ms 61824 KB
giri4 AC 204 ms 61696 KB
giri5 AC 211 ms 62208 KB
giri6 AC 200 ms 62208 KB
giri7 AC 223 ms 62080 KB
giri8 WA 200 ms 61952 KB
giri9 WA 242 ms 62208 KB
maxrand0 AC 185 ms 62336 KB
maxrand1 AC 173 ms 62080 KB
maxrand2 AC 180 ms 62336 KB
maxrand3 AC 176 ms 61952 KB
maxrand4 AC 167 ms 61696 KB
maxrand5 AC 171 ms 61696 KB
maxrand6 AC 172 ms 61696 KB
maxrand7 AC 181 ms 62080 KB
maxrand8 AC 174 ms 61696 KB
maxrand9 AC 183 ms 62080 KB
narashi0 AC 199 ms 61440 KB
narashi1 AC 209 ms 61568 KB
narashi2 AC 216 ms 61696 KB
narashi3 AC 195 ms 61952 KB
narashi4 AC 201 ms 61952 KB
narashi5 AC 189 ms 62080 KB
narashi6 AC 200 ms 61696 KB
narashi7 AC 206 ms 62336 KB
narashi8 AC 224 ms 62080 KB
narashi9 AC 192 ms 61696 KB
ok0 WA 229 ms 69116 KB
ok1 WA 238 ms 70140 KB
ok2 AC 222 ms 67068 KB
ok3 WA 244 ms 70524 KB
ok4 WA 283 ms 65152 KB
ok5 WA 241 ms 67068 KB
ok6 WA 232 ms 67580 KB
ok7 WA 227 ms 65024 KB
ok8 AC 228 ms 68860 KB
ok9 WA 224 ms 67708 KB
ouh0 AC 170 ms 63488 KB
ouh1 WA 208 ms 64256 KB
ouh2 AC 185 ms 64128 KB
ouh3 WA 220 ms 65024 KB
ouh4 AC 249 ms 64640 KB
ouh5 WA 239 ms 67836 KB
ouh6 AC 263 ms 68988 KB
ouh7 WA 237 ms 64128 KB
ouh8 AC 247 ms 67580 KB
ouh9 WA 238 ms 68988 KB
same0 AC 217 ms 62080 KB
same1 AC 215 ms 61824 KB
same2 AC 177 ms 62208 KB
same3 AC 179 ms 62208 KB
same4 AC 184 ms 61696 KB
same5 AC 248 ms 61696 KB
same6 AC 183 ms 61952 KB
same7 AC 208 ms 61696 KB
same8 AC 169 ms 61696 KB
same9 AC 217 ms 62208 KB
sameline0 AC 231 ms 69376 KB
sameline1 AC 273 ms 69888 KB
sameline2 AC 233 ms 67712 KB
sameline3 AC 266 ms 69504 KB
sameline4 AC 257 ms 69504 KB
sameline5 AC 237 ms 69120 KB
sameline6 AC 221 ms 68992 KB
sameline7 AC 261 ms 68992 KB
sameline8 AC 233 ms 68352 KB
sameline9 AC 231 ms 68224 KB
star0 AC 106 ms 62964 KB
star1 AC 100 ms 62836 KB
star2 AC 80 ms 62964 KB
star3 AC 106 ms 62836 KB
star4 AC 101 ms 62964 KB
star5 AC 137 ms 63092 KB
star6 AC 84 ms 63092 KB
star7 AC 105 ms 62836 KB
star8 AC 113 ms 62836 KB
star9 AC 134 ms 63348 KB
supersmall0 AC 6 ms 14592 KB
supersmall1 AC 6 ms 14592 KB
supersmall2 AC 6 ms 14592 KB
supersmall3 AC 6 ms 14592 KB
supersmall4 AC 6 ms 14592 KB
supersmall5 AC 6 ms 14592 KB
supersmall6 AC 6 ms 14592 KB
supersmall7 AC 6 ms 14592 KB
supersmall8 AC 6 ms 14592 KB
supersmall9 AC 7 ms 14592 KB