#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1000;
const int INF = 987654321;
int N, R, X;
vector<int> adj[MAXN+10];
vector<int> V;
bool P[MAXN+10];
int val[MAXN+10];
int dfs(int now, int bef)
{
V.push_back(now);
if(now==X) return 1;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(dfs(nxt, now)) return 1;
}
V.pop_back();
return 0;
}
void dfs2(int now, int bef)
{
int chd=0;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(P[nxt]) continue;
chd++;
}
val[now]=val[bef]+chd;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(P[nxt]) continue;
dfs2(nxt, now);
}
}
int dp[MAXN+10][MAXN+10];
void dfs3(int now, int bef)
{
if(now==R) return;
for(int i=0; i<=N; i++) dp[now][i]=INF;
if(P[now])
{
vector<int> V[MAXN+10];
int pnode=-1;
int chd=0;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(P[nxt])
{
pnode=nxt;
dfs3(nxt, now);
continue;
}
chd++;
dfs3(nxt, now);
for(int i=0; i<=N; i++) V[i].push_back(dp[nxt][i]);
}
assert(pnode!=-1);
for(int i=0; i<=N; i++) sort(V[i].begin(), V[i].end(), greater<int>());
for(int i=0; i<N; i++) for(int j=0; j<V[i].size(); j++)
{
if(i+j<=N) dp[now][i+j]=min(dp[now][i+j], max(V[i+1][j], dp[pnode][i+1]+j));
}
for(int i=chd; i<=N; i++) dp[now][i]=min(dp[now][i], dp[pnode][i-chd+1]+chd);
}
else
{
vector<int> V[MAXN+10];
int chd=0;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
chd++;
dfs3(nxt, now);
for(int i=0; i<=N; i++) V[i].push_back(dp[nxt][i]);
}
for(int i=0; i<=N; i++) sort(V[i].begin(), V[i].end(), greater<int>());
for(int i=0; i<N; i++) for(int j=0; j<V[i].size(); j++)
{
if(i+j<=N) dp[now][i+j]=min(dp[now][i+j], V[i+1][j]);
}
for(int i=chd; i<=N; i++) dp[now][i]=min(dp[now][i], val[now]);
}
//printf("%d : ", now);
//for(int i=0; i<=N; i++) printf("%d ", dp[now][i]); printf("\n");
}
int main()
{
scanf("%d%d%d", &N, &R, &X);
for(int i=1; i<N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(R, R);
for(auto it : V) P[it]=1;
int t=0;
for(int i=1; i<V.size(); i++)
{
dfs2(V[i], V[i]);
if(i+1<V.size())
{
t+=adj[V[i]].size()-2;
val[V[i+1]]=t;
}
}
dfs3(X, X);
printf("%d\n", dp[X][1]);
//dfs(X, R, adj[X].size());
//printf("%d\n", dp[X]-1);
}
Compilation message
mousetrap.cpp: In function 'void dfs3(int, int)':
mousetrap.cpp:77:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0; i<N; i++) for(int j=0; j<V[i].size(); j++)
| ~^~~~~~~~~~~~
mousetrap.cpp:96:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i=0; i<N; i++) for(int j=0; j<V[i].size(); j++)
| ~^~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:121:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i=1; i<V.size(); i++)
| ~^~~~~~~~~
mousetrap.cpp:124:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | if(i+1<V.size())
| ~~~^~~~~~~~~
mousetrap.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | scanf("%d%d%d", &N, &R, &X);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
113 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
620 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
620 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
620 KB |
Output is correct |
| 12 |
Correct |
54 ms |
5100 KB |
Output is correct |
| 13 |
Incorrect |
42 ms |
4972 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
620 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
