# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
374991 | YJU | Mousetrap (CEOI17_mousetrap) | C++14 | 390 ms | 66924 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<cstdio>
#include<vector>
#include<iostream>
using namespace std;
//令 f_i 表示耗子??????入子?后又把把耗子赶回?的最小步?
//取次大儿子?移,因?可以把通往 wi 最大的儿子的路封上,
//耗子就?走向次大儿子。
int m,n,from,to,root,oo,sm[1000500],s[1000500],top,
f[1000500],du[1000500],fa[1000500];
vector<int> g[1000500];
bool e[1000500],asd;
void dfs(int num,int last)
{
fa[num]=last;//??便?理了一?fa??
if(du[num]==0){f[num]=0;return ;}//?界
int h1=0,h2=0;//h1:最大值; h2:次大值
for (int i=0;i<g[num].size();i++)
if (g[num][i]!=last){
dfs(g[num][i],num);
if (f[g[num][i]]>=h1)//注意等于?
{h2=h1;h1=f[g[num][i]];}
}f[num]=h2+du[num]-1;
}
//s??按?序(老鼠->根)存的是老鼠?始?的??到根路?上的所有??
bool check(int k)
{
int sum=0,tmp;
//有??tmp的?故是因?在j的循??k--?WA,同一???的子?的k要求必然相同(感性理解,??)
for(int i=1;i<top;i++){
tmp=0;
for(int j=0;j<g[s[i]].size();j++){
int v=g[s[i]][j];//某棵子?
if(v!=s[i+1]&&//往上走的情?不在?里考?,??在下一次循?
v!=s[i-1]&&//不能走回?路
sm[i]+f[v]+1-(i!=1)>k)//不堵上就?TLE
tmp++;//堵上
}sum+=tmp;k-=tmp;//?操作次?增加,剩余操作次??少
if(k<0||//封堵的?次?>k
sum>i)//管理者的手速不?快
return 0;
}return 1;
}
int main()
{
scanf("%d%d%d",&n,&root,&m);
for (int i=1;i<n;i++){
from=i;to=i+1;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
du[from]++;du[to]++;
}dfs(root,0);
f[root]=0;//?界
for(int i=m;i;i=fa[i])s[++top]=i;
for(int i=top-1;i;i--)sm[i]=sm[i+1]+du[s[i]]-1-(s[i]!=root);
int l=0,r=1e8,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;//二分,?里要+1
}printf("%d",r);
return 0;
}
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... |