# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
309563 | bigg | Mousetrap (CEOI17_mousetrap) | C++14 | 44 ms | 11512 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 = 1e5 + 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> p_ = 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);
p_ = inserts(dp[viz], p_);
}
if(grafo[x].size() == 1) dp[x] = 0;
else{
dp[x] = grafo[x].size() == 2 ? 1 : p_.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... |