Submission #1482119


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

struct LCA{
	vector<vector<int> > g;
	const int MAX_LOG = 22;
	vector<vector<int> > lcc;
	vector<int> dep;
	vector<int> myr;
private:
	void init2(){
		int n = g.size();
		for (int i = 0; i + 1 < MAX_LOG; i++){
			for (int j = 0; j < n; j++){
				if (lcc[i][j] == -1){
					lcc[i + 1][j] = -1;
					continue;
				}
				lcc[i + 1][j] = lcc[i][lcc[i][j]];
			}
		}
	}
public:
	int lca(int a, int b){
		if (dep[a] < dep[b]){
			swap(a, b);
		}
		for (int i = 0; i < MAX_LOG; i++){
			if (((dep[a] - dep[b]) >> i) & 1){
				a = lcc[i][a];
			}
		}
		if (a == b){
			return a;
		}
		for (int i = MAX_LOG - 1; i >= 0; i--){
			if (lcc[i][a] != lcc[i][b]){
				a = lcc[i][a];
				b = lcc[i][b];
			}
		}
		return lcc[0][a];
	}
private:
	int flag_r;
	inline void dfs(int b, int pr = -1, int d = 0){
		for (auto &i : g[b]){
			if (i == pr)continue;
			dfs(i, b, d + 1);
		}
		dep[b] = d;
		lcc[0][b] = pr;
		myr[b] = flag_r;
	}
public:

	void init(vector<vector<int> > &tree, int root = 0){
		g = tree;
		myr.resize(tree.size(), -1);
		flag_r = root;
		lcc.resize(MAX_LOG, vector<int>(g.size(), 0));
		dep.resize(g.size());
		dfs(root);
		init2();
	}
	void init(vector<vector<int> > &tree, vector<int> &root){
		g = tree;
		myr.resize(tree.size(), -1);
		lcc.resize(MAX_LOG, vector<int>(g.size(), 0));
		dep.resize(g.size());
		for (int &i : root){
			if (myr[i] == -1){
				flag_r = i;
				dfs(i);
			}
		}
		init2();
	}
	int dist(int a, int b){ 
		if (myr[a] != myr[b]){
			return -1;
		}
		int lc = lca(a, b);
		return dep[a] + dep[b] - 2 * dep[lc];
	}
};

#define MAX 200002

int n;

int x;
int y;

vector<vector<int> > sigma;
vector<vector<int> > sugim;

LCA sigmaL;
LCA sugimL;
LCA sigmaLL;

bool win[MAX];

vector<vector<int> > vv;
queue<int> q;
vector<int> ord;
bool vis[MAX];

int main(){
	cin >> n;
	cin >> x >> y;
	sigma.resize(n,vector<int>());
	sugim = sigma; 
	vv = sigma;
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		sigma[a].push_back(b);
		sigma[b].push_back(a);
	}
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		sugim[a].push_back(b);
		sugim[b].push_back(a);
	}
	x--;
	y--;
	sugimL.init(sugim,y);
	for (int i = 0; i < n; i++){
		for (int &j : sigma[i]){
			if (i > j)continue;
			int d = sugimL.dist(i, j);
			if (d > 2){
				win[i] = true;
				win[j] = true;
				continue;
			}
			else{
				int ll = sugimL.lca(i, j);
				if (ll != i&&ll != j){
					vv[i].push_back(ll);
					vv[ll].push_back(i);
					vv[j].push_back(ll);
					vv[ll].push_back(j);
				}
				else{
					vv[i].push_back(j);
					vv[j].push_back(i);
				}
			}
		}
	}
	vis[y] = true;
	q.push(y);
	while (!q.empty()){
		int b = q.front();
		q.pop();
		for (int &i : sugim[b]){
			if (!vis[i]){
				vis[i] = true;
				q.push(i);
			}
		}
		ord.push_back(b);
	}
	sigmaL.init(vv, ord);
	for (int i = 0; i < n; i++){
		if (win[i]){
			int a = x;
			int b = i;
			if (sigmaL.myr[a] != sigmaL.myr[b]){
				continue;
			}
			int lc = sugimL.lca(a, b);
			int tim = sigmaL.dist(a, lc);
			int tim2 = sugimL.dist(lc, y);
			if (tim == -1){
				continue;
			}
			if (tim < tim2){
				puts("-1");
				return 0;
			}
		}
	}
	return 0;
	sigmaLL.init(sigma, y);
	int ans = 0;
	for (int i = 0; i < n; i++){
		if (win[i] == false){
			int a = x;
			int b = i;
			if (sigmaL.myr[a] != sigmaL.myr[b]){
				continue;
			}
			int lc = sugimL.lca(a, b);
			int tim = sigmaLL.dist(a, lc);
			int tim2 = sugimL.dist(lc, y);
			int cost = sigmaLL.dist(a, b);
			if (tim > tim2){
				continue;
			}
			if (tim == tim2){
				if (b == lc){
					ans = max(ans, cost);
				}
			}
			if (tim < tim2){
				ans = max(ans, cost + tim2 - tim);
			}
		}
	}
	cout << 2*ans << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User Kmcode
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3971 Byte
Status RE
Exec Time 2113 ms
Memory 262400 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:117:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^
./Main.cpp:125:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1400
Status
AC × 1
WA × 4
AC × 35
WA × 51
TLE × 15
RE × 2
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 TLE 2111 ms 86016 KB
doublestar1 TLE 2111 ms 80292 KB
doublestar2 AC 287 ms 82060 KB
doublestar3 AC 258 ms 78508 KB
doublestar4 AC 280 ms 84852 KB
doublestar5 TLE 2111 ms 87920 KB
doublestar6 TLE 2111 ms 79276 KB
doublestar7 TLE 2111 ms 81828 KB
example0 WA 1 ms 256 KB
example1 WA 1 ms 256 KB
example2 WA 1 ms 256 KB
example3 AC 1 ms 256 KB
example4 WA 1 ms 256 KB
giri0 AC 298 ms 94840 KB
giri1 WA 298 ms 90512 KB
giri2 AC 305 ms 91780 KB
giri3 WA 299 ms 90640 KB
giri4 WA 303 ms 91144 KB
giri5 WA 313 ms 94064 KB
giri6 WA 313 ms 93560 KB
giri7 WA 303 ms 91784 KB
giri8 AC 315 ms 92288 KB
giri9 AC 307 ms 92924 KB
maxrand0 AC 343 ms 81524 KB
maxrand1 AC 335 ms 80508 KB
maxrand2 AC 343 ms 81648 KB
maxrand3 AC 329 ms 79620 KB
maxrand4 AC 323 ms 78100 KB
maxrand5 AC 331 ms 78480 KB
maxrand6 AC 328 ms 78228 KB
maxrand7 AC 335 ms 80380 KB
maxrand8 AC 331 ms 77972 KB
maxrand9 AC 371 ms 80128 KB
narashi0 WA 299 ms 89368 KB
narashi1 WA 305 ms 90128 KB
narashi2 WA 298 ms 89752 KB
narashi3 WA 302 ms 91656 KB
narashi4 WA 316 ms 92920 KB
narashi5 WA 313 ms 92164 KB
narashi6 WA 314 ms 91904 KB
narashi7 WA 313 ms 93812 KB
narashi8 WA 318 ms 93556 KB
narashi9 WA 301 ms 90384 KB
ok0 AC 325 ms 93444 KB
ok1 AC 332 ms 94972 KB
ok2 WA 327 ms 94588 KB
ok3 AC 336 ms 96116 KB
ok4 AC 315 ms 93196 KB
ok5 AC 335 ms 95856 KB
ok6 AC 322 ms 93696 KB
ok7 AC 319 ms 92176 KB
ok8 WA 339 ms 96240 KB
ok9 AC 320 ms 92048 KB
ouh0 WA 271 ms 91560 KB
ouh1 AC 300 ms 93964 KB
ouh2 WA 285 ms 87740 KB
ouh3 AC 307 ms 93960 KB
ouh4 WA 313 ms 93708 KB
ouh5 AC 308 ms 90404 KB
ouh6 WA 305 ms 92308 KB
ouh7 AC 306 ms 91424 KB
ouh8 WA 316 ms 95100 KB
ouh9 AC 314 ms 93196 KB
same0 WA 300 ms 92288 KB
same1 WA 294 ms 91400 KB
same2 WA 303 ms 93812 KB
same3 WA 309 ms 93684 KB
same4 WA 294 ms 90132 KB
same5 WA 296 ms 90384 KB
same6 WA 300 ms 91908 KB
same7 WA 296 ms 90512 KB
same8 WA 293 ms 89624 KB
same9 WA 306 ms 93304 KB
sameline0 WA 321 ms 95888 KB
sameline1 WA 333 ms 99696 KB
sameline2 WA 321 ms 95240 KB
sameline3 WA 324 ms 96264 KB
sameline4 WA 339 ms 98552 KB
sameline5 WA 324 ms 96648 KB
sameline6 WA 321 ms 94348 KB
sameline7 WA 330 ms 97408 KB
sameline8 WA 335 ms 97780 KB
sameline9 WA 331 ms 97012 KB
star0 TLE 2112 ms 97020 KB
star1 TLE 2110 ms 96640 KB
star2 TLE 2112 ms 97020 KB
star3 TLE 2112 ms 96512 KB
star4 TLE 2112 ms 97400 KB
star5 TLE 2112 ms 98416 KB
star6 TLE 2111 ms 100212 KB
star7 TLE 2112 ms 96892 KB
star8 TLE 2112 ms 96640 KB
star9 TLE 2113 ms 99816 KB
supersmall0 AC 1 ms 256 KB
supersmall1 AC 1 ms 256 KB
supersmall2 AC 1 ms 256 KB
supersmall3 WA 1 ms 256 KB
supersmall4 AC 1 ms 256 KB
supersmall5 WA 1 ms 256 KB
supersmall6 RE 270 ms 262400 KB
supersmall7 RE 388 ms 262400 KB
supersmall8 WA 1 ms 256 KB
supersmall9 WA 1 ms 256 KB