/**
Template created by Danel Batyrbek
All rights are reserved 2018 (lol)
*/
#include <bits/stdc++.h>
#define speed_up ios_base :: sync_with_stdio(0);cin.tie(0)
#define fr first
#define sc second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define all(x) x.begin(), x.end()
#define debug(x) cerr << x << '\n';
#define YES "YES"
#define NO "NO"
#define skip continue
#define left(x) x << 1
#define rght(x) x << 1 | 1
#define forn(x, y, z) for(int x = y; x <= z; ++ x)
#define for1(x, y, z) for(int x = y; x >= z; -- x)
#define fname ""
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef double ld;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int N3 = 1e3 + 10;
const int INF = 2e9 + 10;
const ll LINF = 2e18;
int n, a, b, cnt1[N], cnt2[N], dp[N], depth1[N], depth2[N], ans;
bool u[N];
vector <pair <pii, int> > v1[N], v2[N];
queue <pii> q;
void init(){
forn(i, 1, n) u[i] = 0;
}
void dfs(int x, vector <pair <pii, int> > v[], int dep[], int arr[]){
u[x] = 1;
for(pair <pii, int> to : v[x]){
if(!u[to.sc]){
dep[to.sc] = dep[x] + 1;
dfs(to.sc, v, dep, arr);
arr[x] += arr[to.sc];
}
}
for(pair <pii, int> to : v[x]){
dep[x] = max(dep[x], dep[to.sc]);
}
arr[x] ++;
}
int main(){
#ifdef DEBUG
freopen("in", "r", stdin);
#else
if(fname != ""){
freopen(fname".in", "r", stdin);
freopen(fname".out", "w", stdout);
}
#endif
cin >> n >> a >> b;
forn(i, 1, n - 1){
dp[i] = INF;
int x, y;
cin >> x >> y;
v1[x].pb(mkp(mkp(0, 0), y));
v1[y].pb(mkp(mkp(0, 0), x));
v2[x].pb(mkp(mkp(0, 0), y));
v2[y].pb(mkp(mkp(0, 0), x));
}
dp[n] = INF;
dfs(a, v1, depth1, cnt1);
init();
dfs(b, v2, depth2, cnt2);
forn(i, 1, n){
for(pair <pii, int> x : v1[i]){
x.fr.fr = -depth1[x.sc];
x.fr.sc = -cnt1[x.sc];
}
for(pair <pii, int> x : v2[i]){
x.fr.fr = -depth2[x.sc];
x.fr.sc = -cnt2[x.sc];
}
sort(all(v1[i]));
sort(all(v2[i]));
}
q.push(mkp(a, a));
q.push(mkp(b, b));
dp[a] = dp[b] = 0;
while(q.size()){
pii x = q.front();
q.pop();
int cnt = 1;
if(x.sc == a){
for(pair <pii, int> to : v1[x.fr]){
if(dp[to.sc] > dp[x.fr] + cnt){
dp[to.sc] = dp[x.fr] + cnt;
cnt ++;
q.push(mkp(to.sc, a));
}
}
} else {
for(pair <pii, int> to : v2[x.fr]){
if(dp[to.sc] > dp[x.fr] + cnt){
dp[to.sc] = dp[x.fr] + cnt;
cnt ++;
q.push(mkp(to.sc, b));
}
}
}
}
forn(i, 1, n) ans = max(ans, dp[i]);
cout << ans;
return 0;
}
Compilation message
torrent.cpp: In function 'int main()':
torrent.cpp:65:14: warning: comparison with string literal results in unspecified behaviour [-Waddress]
if(fname != ""){
^
torrent.cpp:66:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(fname".in", "r", stdin);
^
torrent.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(fname".out", "w", stdout);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
16812 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
