# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1241228 | knhatdev | Mousetrap (CEOI17_mousetrap) | C++20 | 220 ms | 125688 KiB |
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define task ""
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, a[N], dp[N], par[N], ans, t, m;
vector<ii> vec[N];
vector<int> g[N];
void dfs(int u, int p = -1)
{
dp[u] = 1;
for(int v : g[u])
{
if(v == p) continue;
dfs(v, u);
par[v] = u;
dp[u] = max(dp[u], dp[v] + 1);
vec[u].push_back(ii(dp[v], v));
}
sort(vec[u].begin(), vec[u].end(), [](ii x, ii y)
{
return x.fi > y.fi;
});
}
void dfs2(int u)
{
ans++;
if(vec[u].size() <= 1)
{
ans++;
return;
}
ans += vec[u].size() - 1;
dfs2(vec[u][1].se);
}
main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(task ".inp", "r")){
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
cin >> n >> t >> m;
for(int i = 1; i < n; i++)
{
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(t);
dfs2(m);
ans--;
int tmp = par[m];
while(tmp != t)
{
ans += vec[tmp].size() - 1;
tmp = par[tmp];
}
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |