oj.uz

Submission #304665

# Submission time Handle Problem Language Result Execution time Memory
304665 2020-09-21T17:03:44 Z JovanK26 Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 411 ms 122720 KB 
#include <bits/stdc++.h>

using namespace std;
vector<int> tree[1000001];
int prt[1000001];
int f[1000001];
vector< pair<int,int> > subtrees;
int ispath[1000001];
int n,m,t;
int dfs1(int cur,int prev)
{
    int par=-1;
    for(int i=0;i<tree[cur].size();i++)
    {
        if(tree[cur][i]==prev)par=prev;
    }
    if(par!=-1)
    {
        tree[cur].erase(tree[cur].begin()+par);
    }
    prt[cur]=prev;
    int rez=-1;
    if(cur==m)rez=0;
    for(int i=0;i<tree[cur].size();i++)
    {
        rez=max(rez,dfs1(tree[cur][i],cur));
    }
    ispath[cur]=rez;
    if(rez==-1)return rez;
    return rez+1;
}
void dfs2(int cur,int w)
{
    if(tree[cur].size()==0)
    {
        f[cur]=w;
        return;
    }
    if(ispath[cur]==-1)
    {
        int neww=w+tree[cur].size();
        for(int i=0;i<tree[cur].size();i++)
        {
            dfs2(tree[cur][i],neww);
        }
        if(tree[cur].size()==1)
        {
            f[cur]=w+1;
        }
        int best=-1;
        int sbest=-1;
        for(int i=0;i<tree[cur].size();i++)
        {
            if(f[tree[cur][i]]>best)
            {
                sbest=best;
                best=f[tree[cur][i]];
                continue;
            }
            if(f[tree[cur][i]]>sbest)
            {
                sbest=f[tree[cur][i]];
            }
        }
        f[cur]=sbest;
        return;
    }
    int neww=w+tree[cur].size()-1;
    if(cur==t)neww=0;
    if(cur==m)neww++;
    for(int i=0;i<tree[cur].size();i++)
    {
        dfs2(tree[cur][i],neww);
    }
    if(cur==t)return;
    for(int i=0;i<tree[cur].size();i++)
    {
        if(ispath[tree[cur][i]]==-1)
        {
            subtrees.push_back(make_pair(ispath[cur],f[tree[cur][i]]));
        }
    }
}
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    m--;
    t--;
    int x,y;
    for(int i=0;i<n-1;i++)
    {
        cin >> x >> y;
        x--;
        y--;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    int pathl=dfs1(t,-1);
    dfs2(t,0);
    sort(subtrees.begin(),subtrees.end());
    int l=0;
    int r=n;
    int med;
    while(l<r)
    {
        med=(l+r)/2;
        x=0;
        y=0;
        int pt=0;
        for(int i=0;i<pathl;i++)
        {
            if(pt>=subtrees.size())
            {
                r=med;
                break;
            }
            x++;
            int ydelta=0;
            while(pt<subtrees.size() && subtrees[pt].first<=i)
            {
               if(subtrees[pt].second+y>med)
               {
                   ydelta++;
                   x--;
               }
               pt++;
            }
            y+=ydelta;
            if(x<0 || y>med)
            {
                l=med+1;
                break;
            }
        }
    }
    cout << l;
    return 0;
}

Compilation message

mousetrap.cpp: In function 'int dfs1(int, int)':
mousetrap.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs2(int, int)':
mousetrap.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i=0;i<tree[cur].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0;i<tree[cur].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             if(pt>=subtrees.size())
      |                ~~^~~~~~~~~~~~~~~~~
mousetrap.cpp:123:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             while(pt<subtrees.size() && subtrees[pt].first<=i)
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 48248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 411 ms 122720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 48248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 48248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -