# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
309564 | bigg | Mousetrap (CEOI17_mousetrap) | C++14 | 910 ms | 73464 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
vector<int> grafo[MAXN];
int dp[MAXN];
pair<int, int > inserts(int x, pair<int, int> p){
if(x >= p.first) swap(p.first, p.second), p.first = x;
else if(x > p.second) p.second = x;
return p;
}
void dfs(int x, int p){
pair<int, int> par = make_pair(-1, -1);
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i];
if(viz == p) continue;
dfs(viz, x);
par = inserts(dp[viz], par);
}
if(grafo[x].size() == 1) dp[x] = 0;
else{
dp[x] = (grafo[x].size() == 2) ? 1 : par.second + grafo[x].size() - 1;
}
//printf("%d\n", dp[x]);
}
int n, t, m;
int main(){
scanf("%d %d %d", &n, &t, &m);
if(n == 1 || t == m){
printf("0\n");
return 0;
}
for(int i = 1; i < n; i++){
int u, v;
scanf("%d %d", &u, &v);
grafo[u].push_back(v);
grafo[v].push_back(u);
}
dfs(t, 0);
printf("%d\n",dp[m] );
}
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... |