oj.uz

Submission #1096065

# Submission time Handle Problem Language Result Execution time Memory
1096065 2024-10-03T16:37:29 Z Antares Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 929 ms 170748 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)
    {
        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

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 10 ms 24152 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 10 ms 23992 KB Output is correct
4 Correct 11 ms 24156 KB Output is correct
5 Correct 9 ms 24156 KB Output is correct
6 Correct 11 ms 24140 KB Output is correct
7 Correct 11 ms 24180 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 10 ms 24156 KB Output is correct
10 Correct 11 ms 24140 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 63164 KB Output is correct
2 Correct 410 ms 59372 KB Output is correct
3 Correct 929 ms 64592 KB Output is correct
4 Correct 346 ms 44188 KB Output is correct
5 Correct 835 ms 64340 KB Output is correct
6 Correct 923 ms 68800 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24152 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 10 ms 23992 KB Output is correct
4 Correct 11 ms 24156 KB Output is correct
5 Correct 9 ms 24156 KB Output is correct
6 Correct 11 ms 24140 KB Output is correct
7 Correct 11 ms 24180 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 10 ms 24156 KB Output is correct
10 Correct 11 ms 24140 KB Output is correct
11 Correct 10 ms 24156 KB Output is correct
12 Correct 11 ms 24172 KB Output is correct
13 Correct 13 ms 24156 KB Output is correct
14 Correct 10 ms 24152 KB Output is correct
15 Correct 10 ms 24156 KB Output is correct
16 Correct 11 ms 24156 KB Output is correct
17 Correct 11 ms 24132 KB Output is correct
18 Correct 10 ms 24152 KB Output is correct
19 Correct 10 ms 24156 KB Output is correct
20 Correct 10 ms 24148 KB Output is correct
21 Correct 11 ms 24156 KB Output is correct
22 Correct 10 ms 24108 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24152 KB Output is correct
2 Correct 11 ms 24156 KB Output is correct
3 Correct 10 ms 23992 KB Output is correct
4 Correct 11 ms 24156 KB Output is correct
5 Correct 9 ms 24156 KB Output is correct
6 Correct 11 ms 24140 KB Output is correct
7 Correct 11 ms 24180 KB Output is correct
8 Correct 11 ms 24156 KB Output is correct
9 Correct 10 ms 24156 KB Output is correct
10 Correct 11 ms 24140 KB Output is correct
11 Correct 475 ms 63164 KB Output is correct
12 Correct 410 ms 59372 KB Output is correct
13 Correct 929 ms 64592 KB Output is correct
14 Correct 346 ms 44188 KB Output is correct
15 Correct 835 ms 64340 KB Output is correct
16 Correct 923 ms 68800 KB Output is correct
17 Correct 10 ms 24156 KB Output is correct
18 Correct 11 ms 24172 KB Output is correct
19 Correct 13 ms 24156 KB Output is correct
20 Correct 10 ms 24152 KB Output is correct
21 Correct 10 ms 24156 KB Output is correct
22 Correct 11 ms 24156 KB Output is correct
23 Correct 11 ms 24132 KB Output is correct
24 Correct 10 ms 24152 KB Output is correct
25 Correct 10 ms 24156 KB Output is correct
26 Correct 10 ms 24148 KB Output is correct
27 Correct 11 ms 24156 KB Output is correct
28 Correct 10 ms 24108 KB Output is correct
29 Correct 11 ms 24156 KB Output is correct
30 Correct 472 ms 76460 KB Output is correct
31 Correct 543 ms 76652 KB Output is correct
32 Correct 557 ms 155984 KB Output is correct
33 Correct 565 ms 170748 KB Output is correct
34 Correct 868 ms 77508 KB Output is correct
35 Correct 868 ms 77600 KB Output is correct
36 Correct 850 ms 93940 KB Output is correct
37 Correct 926 ms 94032 KB Output is correct
38 Correct 754 ms 92580 KB Output is correct
39 Correct 747 ms 92688 KB Output is correct
40 Correct 696 ms 92756 KB Output is correct