# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259841 | Kastanda | Mousetrap (CEOI17_mousetrap) | C++11 | 1312 ms | 229240 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.
// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, root, st, SM, P[N], M[N], dp[N];
vector < int > Adj[N], V[N];
void DFS(int v, int p = 0)
{
P[v] = p;
for (int i = 0; i < (int)Adj[v].size(); i ++)
if (Adj[v][i] == p)
Adj[v].erase(Adj[v].begin() + i);
if (st == v) M[v] = 1;
for (int u : Adj[v])
DFS(u, v), M[v] |= M[u];
if (v == root)
{
int w = -1;
for (int u : Adj[v])
if (M[u]) w = u;
Adj[v] = {w};
}
}
void DFS2(int v, int p = 0)
{
if (v != root)
SM += (int)Adj[v].size() - (M[v] && v != st);
for (int u : Adj[v])
DFS2(u, v);
if (v != root)
SM -= (int)Adj[v].size() - (M[v] && v != st);
for (int u : Adj[v])
if (!M[u])
V[v].push_back(dp[u]);
sort(V[v].begin(), V[v].end());
reverse(V[v].begin(), V[v].end());
if (M[v])
return ;
if (!Adj[v].size())
{
dp[v] = SM;
return ;
}
if (Adj[v].size() == 1)
{
dp[v] = SM + 1;
return ;
}
dp[v] = V[v][1];
}
inline bool Solve(int md)
{
int nw = st, cnt = 1;
while (nw != root)
{
int c = 0;
for (int val : V[nw])
if (val > md)
cnt --, c ++;
md -= c;
if (cnt < 0 || md < 0)
return 0;
nw = P[nw];
cnt ++;
}
return 1;
}
int main()
{
scanf("%d%d%d", &n, &root, &st);
for (int i = 1; i < n; i ++)
{
int v, u;
scanf("%d%d", &v, &u);
Adj[v].push_back(u);
Adj[u].push_back(v);
}
DFS(root);
DFS2(root);
int le = -1, ri = n, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Solve(md))
ri = md;
else
le = md;
}
return !printf("%d\n", ri);
}
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... |