Submission #1096065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096065		Antares	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	929 ms	170748 KiB

mousetrap

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#define inf 2000000
using namespace std;
vector <int> v[1000001];
bitset <1000001> vis;
int n,m,t,k,nr;
int val_noduri[1000001],fr[1000001],noduri[1000001],vecini[1000001],last_vecini[1000001],p[1000001],dp[1000001];
struct pozitie
{
    int val,pos,lazy;
} sol;
struct seg_tree
{
    pozitie aint[4000001];
    void f (int nod,bool ok)
    {
        if ((ok&&aint[2*nod].val>=aint[2*nod+1].val)||(!ok&&aint[2*nod].val<=aint[2*nod+1].val))
            aint[nod]=aint[2*nod];
        else
            aint[nod]=aint[2*nod+1];
        aint[nod].lazy=0;
    }
    void build (int nod,int st,int dr,int v[],bool ok)
    {
        aint[nod].lazy=0;
        if (st==dr)
        {
            aint[nod].val=v[st];
            aint[nod].pos=st;
        }
        else
        {
            int mij=(st+dr)/2;
            build (2*nod,st,mij,v,ok);
            build (2*nod+1,mij+1,dr,v,ok);
            f (nod,ok);
        }
    }
    void propagate (int nod,int st,int dr)
    {
        if (st!=dr)
        {
            aint[2*nod].val+=aint[nod].lazy;
            aint[2*nod+1].val+=aint[nod].lazy;
            aint[2*nod].lazy+=aint[nod].lazy;
            aint[2*nod+1].lazy+=aint[nod].lazy;
        }
        aint[nod].lazy=0;
    }
    void update (int nod,int st,int dr,int a,int b,int x,bool ok)
    {
        if (a>b)
            return ;
        propagate (nod,st,dr);
        if (st>=a&&dr<=b)
        {
            aint[nod].val+=x;
            aint[nod].lazy+=x;
        }
        else
        {
            int mij=(st+dr)/2;
            if (a<=mij)
                update (2*nod,st,mij,a,b,x,ok);
            if (b>mij)
                update (2*nod+1,mij+1,dr,a,b,x,ok);
            f (nod,ok);
        }
    }
    pozitie query ()
    {
        return aint[1];
    }
};
seg_tree aint_noduri,aint_vecini;
void dfs (int nod,int t)
{
    p[nod]=t;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (vecin!=t)
            dfs (vecin,nod);
    }
}
void dfs_dp (int nod,int t)
{
    int max1=0,max2=0,nr=0;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (vecin==t)
            continue;
        nr++;
        dfs_dp (vecin,nod);
        if (dp[vecin]>=max1)
        {
            max2=max1;
            max1=dp[vecin];
        }
        else if (dp[vecin]>max2)
            max2=dp[vecin];
    }
    dp[nod]=max2+nr;
}
void read ()
{
    cin>>n>>t>>m;
    int x,y;
    for (int i=1; i<n; i++)
    {
        cin>>x>>y;
        v[x].push_back (y);
        v[y].push_back (x);
    }
}
void get_nodes ()
{
    int pos=m;
    k=0;
    while (pos!=t)
    {
        k++;
        noduri[k]=pos;
        val_noduri[k]=k;
        vis[pos]=1;
        pos=p[pos];
    }
    vis[t]=1;
    reverse (noduri+1,noduri+k+1);
    reverse (val_noduri+1,val_noduri+k+1);
    aint_noduri.build (1,1,k,val_noduri,0);
}
void get_vecini ()
{
    int nrant;
    nr=0;
    for (int i=1; i<=k; i++)
    {
        nrant=nr;
        for (int j=0; j<v[noduri[i]].size (); j++)
        {
            int vecin=v[noduri[i]][j];
            if (!vis[vecin])
            {
                dfs_dp (vecin,noduri[i]);
                vecini[++nr]=dp[vecin];
                fr[nr]=i;
            }
        }
        for (int j=nrant+1; j<=nr; j++)
            vecini[j]+=nr;
        last_vecini[i]=nr;
    }
    if (nr>0)
        aint_vecini.build (1,1,nr,vecini,1);
}
void solve ()
{
    if (nr==0)
    {
        cout<<0;
        exit (0);
    }
    int nrvec=min (nr,k),minim=1,maxim=0,pos,nrc=0;
    while (nrvec>=0&&minim>=0)
    {
        sol=aint_vecini.query ();
        maxim=sol.val;
        pos=sol.pos;
        if (maxim<=nrc)
        {
            maxim=nrc;
            break;
        }
        aint_noduri.update (1,1,k,1,fr[pos],-1,0);
        sol=aint_noduri.query ();
        minim=sol.val;
        if (minim<0)
            break;

        nrvec--;
        nrc++;
        aint_vecini.update (1,1,nr,pos,pos,-inf,1);
        aint_vecini.update (1,1,nr,1,last_vecini[fr[pos]-1],1,1);
    }
    cout<<maxim;
}
int main ()
{
    read ();
    dfs (t,0);
    get_nodes ();
    get_vecini ();
    solve ();
    return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0; i<v[nod].size (); i++)
      |                   ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs_dp(int, int)':
mousetrap.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i=0; i<v[nod].size (); i++)
      |                   ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void get_vecini()':
mousetrap.cpp:144:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int j=0; j<v[noduri[i]].size (); j++)
      |                       ~^~~~~~~~~~~~~~~~~~~~~

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