oj.uz

Submission #1096068

# Submission time Handle Problem Language Result Execution time Memory
1096068 2024-10-03T16:46:44 Z Antares Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 938 ms 164052 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 11 ms 24136 KB Output is correct
3 Correct 9 ms 24156 KB Output is correct
4 Correct 10 ms 24152 KB Output is correct
5 Correct 10 ms 24152 KB Output is correct
6 Correct 10 ms 24052 KB Output is correct
7 Correct 9 ms 24156 KB Output is correct
8 Correct 9 ms 24080 KB Output is correct
9 Correct 9 ms 24152 KB Output is correct
10 Correct 9 ms 24028 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 73824 KB Output is correct
2 Correct 429 ms 68396 KB Output is correct
3 Correct 923 ms 74576 KB Output is correct
4 Correct 391 ms 49488 KB Output is correct
5 Correct 899 ms 74420 KB Output is correct
6 Correct 890 ms 72428 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 11 ms 24136 KB Output is correct
3 Correct 9 ms 24156 KB Output is correct
4 Correct 10 ms 24152 KB Output is correct
5 Correct 10 ms 24152 KB Output is correct
6 Correct 10 ms 24052 KB Output is correct
7 Correct 9 ms 24156 KB Output is correct
8 Correct 9 ms 24080 KB Output is correct
9 Correct 9 ms 24152 KB Output is correct
10 Correct 9 ms 24028 KB Output is correct
11 Correct 9 ms 24152 KB Output is correct
12 Correct 11 ms 24156 KB Output is correct
13 Correct 11 ms 24156 KB Output is correct
14 Correct 11 ms 24156 KB Output is correct
15 Correct 12 ms 24156 KB Output is correct
16 Correct 10 ms 24156 KB Output is correct
17 Correct 11 ms 24156 KB Output is correct
18 Correct 9 ms 24156 KB Output is correct
19 Correct 9 ms 24156 KB Output is correct
20 Correct 9 ms 24156 KB Output is correct
21 Correct 9 ms 24152 KB Output is correct
22 Correct 13 ms 24156 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24156 KB Output is correct
2 Correct 11 ms 24136 KB Output is correct
3 Correct 9 ms 24156 KB Output is correct
4 Correct 10 ms 24152 KB Output is correct
5 Correct 10 ms 24152 KB Output is correct
6 Correct 10 ms 24052 KB Output is correct
7 Correct 9 ms 24156 KB Output is correct
8 Correct 9 ms 24080 KB Output is correct
9 Correct 9 ms 24152 KB Output is correct
10 Correct 9 ms 24028 KB Output is correct
11 Correct 481 ms 73824 KB Output is correct
12 Correct 429 ms 68396 KB Output is correct
13 Correct 923 ms 74576 KB Output is correct
14 Correct 391 ms 49488 KB Output is correct
15 Correct 899 ms 74420 KB Output is correct
16 Correct 890 ms 72428 KB Output is correct
17 Correct 9 ms 24152 KB Output is correct
18 Correct 11 ms 24156 KB Output is correct
19 Correct 11 ms 24156 KB Output is correct
20 Correct 11 ms 24156 KB Output is correct
21 Correct 12 ms 24156 KB Output is correct
22 Correct 10 ms 24156 KB Output is correct
23 Correct 11 ms 24156 KB Output is correct
24 Correct 9 ms 24156 KB Output is correct
25 Correct 9 ms 24156 KB Output is correct
26 Correct 9 ms 24156 KB Output is correct
27 Correct 9 ms 24152 KB Output is correct
28 Correct 13 ms 24156 KB Output is correct
29 Correct 9 ms 24156 KB Output is correct
30 Correct 500 ms 70168 KB Output is correct
31 Correct 474 ms 69996 KB Output is correct
32 Correct 515 ms 149516 KB Output is correct
33 Correct 537 ms 164052 KB Output is correct
34 Correct 938 ms 71248 KB Output is correct
35 Correct 888 ms 71248 KB Output is correct
36 Correct 906 ms 87672 KB Output is correct
37 Correct 882 ms 87632 KB Output is correct
38 Correct 765 ms 86292 KB Output is correct
39 Correct 782 ms 86096 KB Output is correct
40 Correct 720 ms 86280 KB Output is correct