oj.uz

Submission #374991

# Submission time Handle Problem Language Result Execution time Memory
374991 2021-03-08T18:40:39 Z YJU Mousetrap (CEOI17_mousetrap) C++14
20 / 100
 390 ms 66924 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 20 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 390 ms 66924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 20 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Correct 17 ms 23920 KB Output is correct
12 Correct 17 ms 23916 KB Output is correct
13 Correct 17 ms 23916 KB Output is correct
14 Correct 18 ms 24044 KB Output is correct
15 Correct 17 ms 23916 KB Output is correct
16 Correct 17 ms 23916 KB Output is correct
17 Incorrect 18 ms 23916 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 20 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 16 ms 23916 KB Output is correct
11 Incorrect 390 ms 66924 KB Output isn't correct
12 Halted 0 ms 0 KB -