Submission #1096068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096068		Antares	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	938 ms	164052 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) ///nu avem vecini => 0 operatii
    {
        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++; ///daca toate vecinii au fost eliminati sau e mai bine sa mearga direct in t nrc va fi nr de operatii facute
        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 ()
{
    /**
     nod
   /  |  \
   v1 v2 v3
   dp[nod]=costul minim ca soricelul sa fie obligat sa ajunga in dp[t[nod]]
   dp[m]=max2 (dp[fiu])+nrfii-2 (fara m v2 si m v1)+1 (m v1)+1 (m v2)=max2 (dp[fiu])+nrfii
   Avem drumul de la t la m. Soarecele merge de dist (m-t) ori. La fiecare pas, se pot dezactiva vecini de pe lantul t-m (la un nod de m-nod ori). Cat timpse poate se alege maximul.
   Maximul de la vecini se calculeaza cu dp. La dp se adauga vecinii din stanga vecinului (tb sa fie dezactivati si ei cand soarecele ajunge la acel vecin, restul nu mai conteaza; a trecut de ei)
   La vecinii din stanga se aduna si cate operatii s-au facut
   2 aint-uri: unul pt vecini (maximul, update pe prefix+1, eliminare maxim) si unul pt nodurile de pe lant (cate operatii se pot face pe sufixul nod-m)
    **/
    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