Submission #374991

#	Time	Username	Problem	Language	Result	Execution time	Memory
374991		YJU	Mousetrap (CEOI17_mousetrap)	C++14	20 / 100	390 ms	66924 KiB

mousetrap

#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)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:17:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (int i=0;i<g[num].size();i++)
      |                ~^~~~~~~~~~~~~~
mousetrap.cpp: In function 'bool check(int)':
mousetrap.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int j=0;j<g[s[i]].size();j++){
      |                 ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d%d%d",&n,&root,&m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%d%d",&from,&to);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35