Submission #304708

#	Time	Username	Problem	Language	Result	Execution time	Memory
304708		JovanK26	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1045 ms	158584 KiB

mousetrap

#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=i;
    }
    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;
            return;
        }
        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 >> t >> m;
    m--;
    t--;
    int a,b;
    for(int i=0;i<n-1;i++)
    {
        cin >> a >> b;
        a--;
        b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    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;
        int x=0;
        int 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<<'\n';
    return 0;
}

Compilation message (stderr)

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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<tree[cur].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<tree[cur].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:117: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]
  117 |             if(pt>=subtrees.size())
      |                ~~^~~~~~~~~~~~~~~~~
mousetrap.cpp:124: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]
  124 |             while(pt<subtrees.size() && subtrees[pt].first<=i)
      |                   ~~^~~~~~~~~~~~~~~~

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