Submission #1355436

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
typedef pair<int,int> pii;
int n, x, y, dep[200005], par[20][200005];
int da[200005], db[200005];

vector<int> ra[200005], rb[200005];
vector<pii> red;

queue<int> q;

void calc (int cur, int prv) {
	dep[cur] = dep[prv] + 1;
	par[0][cur] = prv;
	for(auto &nxt : rb[cur]) {
		if(nxt == prv) continue;
		calc(nxt, cur);
	}
}

int getdist (int A, int B) {
	if(dep[A] < dep[B]) swap(A, B);
	int ret = 0;
	for(int i=20;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A]; ret += (1<<i);
		}
	}
	if(A == B) return ret;
	for(int i=20;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
			ret += (1<<i) * 2;
		}
	}
	return ret + 2;
}

int main() {
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		red.push_back({A, B});
		ra[A].push_back(B);
		ra[B].push_back(A);
	}
	for(int i=1;i<n;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		rb[A].push_back(B);
		rb[B].push_back(A);
	}
	calc(1, 0);
	for(int k=1;k<20;k++) {
		for(int i=1;i<=n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
	for(int i=1;i<=n;i++) {da[i] = inf; db[i] = inf;}
	db[y] = 2; q.push(y);
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(auto &nxt : rb[cur]) {
			if(db[nxt] == inf) {
				db[nxt] = db[cur] + 2;
				q.push(nxt);
			}
		}
	}
	da[x] = 1; q.push(x);
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(auto &nxt : ra[cur]) {
			if(da[nxt] == inf && db[nxt] > da[cur] + 2) {
				da[nxt] = da[cur] + 2;
				q.push(nxt);
			}
		}
	}
	for(auto &T : red) {
		int A = T.first, B = T.second;
		if(getdist(A, B) >= 3 && (da[A] != inf && da[B] != inf)) {
			puts("-1"); return 0;
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++) {
		if(da[i] != inf) ans = max(ans, db[i]);
	}
	printf("%d\n",ans-2);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&x,&y);
                          ^
./Main.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^
./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

Judge Result