oj.uz

Submission #1095166

# Submission time Handle Problem Language Result Execution time Memory
1095166 2024-10-01T13:07:36 Z HoriaHaivas Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 697 ms 149120 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct Node
{
    int maxval;
    int maxvalpoz;
    int minval;
    int minvalpoz;
    int lazy;
};

int dp[1000005]; /// dp[u] = costul sa il fortam pe soricel sa se intoarca la u
vector<int> nodes[1000005];
int depth[1000005];
int p[1000005];
int nxt[1000005];
int variante[1000005];
int lim[1000005];
int leftie[1000005];
int rightie[1000005];
int n,t,m,cnt;
const int INF=1e9;

///AINT
class AINT
{
private:
    Node aint[4000005];



public:
    void prop(int val)
    {
        if (aint[val].lazy==0)
            return;
        aint[val].maxval+=aint[val].lazy;
        aint[val].minval+=aint[val].lazy;
        if (val*2+1<=4*n)
        {
            aint[val*2].lazy+=aint[val].lazy;
            aint[val*2+1].lazy+=aint[val].lazy;
        }
        aint[val].lazy=0;
    }
    void build(int l, int r, int val, int num)
    {
        if (l==r)
        {
            if (num==1)
            {
                aint[val]= {variante[l],l,variante[l],l,0};
            }
            else
            {
                aint[val]= {lim[l],l,lim[l],l,0};
            }
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2,num);
        build(mid+1,r,val*2+1,num);
        aint[val]=combine(aint[val*2],aint[val*2+1]);
    }
    void lazy_update(int l, int r, int val, int qa, int qb, int x)
    {
        prop(val);
        if (qa<=l && r<=qb)
        {
            aint[val].lazy+=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (qa<=mid)
            lazy_update(l,mid,val*2,qa,qb,x);
        if (qb>mid)
            lazy_update(mid+1,r,val*2+1,qa,qb,x);
        prop(val*2);
        prop(val*2+1);
        aint[val]=combine(aint[val*2],aint[val*2+1]);
    }
    Node query(int l, int r, int val, int qa, int qb)
    {
        prop(val);
        if (qa<=l && r<=qb)
        {
            return aint[val];
        }
        Node ans;
        int mid;
        ans= {-INF,0,INF,0,0};
        mid=(l+r)/2;
        if (qa<=mid)
            ans=combine(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=combine(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }
    void disable(int l, int r, int val, int poz)
    {
        prop(val);
        if (l==r)
        {
            aint[val]= {-INF,0,INF,0,0};
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (poz<=mid)
            disable(l,mid,val*2,poz);
        else
            disable(mid+1,r,val*2+1,poz);
        prop(val*2);
        prop(val*2+1);
        aint[val]=combine(aint[val*2],aint[val*2+1]);
    }
    Node combine(Node a, Node b)
    {
        Node c;
        if (a.minval!=b.minval)
        {
            if (a.minval<b.minval)
            {
                c.minval=a.minval;
                c.minvalpoz=a.minvalpoz;
            }
            else
            {
                c.minval=b.minval;
                c.minvalpoz=b.minvalpoz;
            }
        }
        else
        {
            if (a.minvalpoz<b.minvalpoz)
            {
                c.minval=a.minval;
                c.minvalpoz=a.minvalpoz;
            }
            else
            {
                c.minval=b.minval;
                c.minvalpoz=b.minvalpoz;
            }
        }
        if (a.maxval!=b.maxval)
        {
            if (a.maxval>b.maxval)
            {
                c.maxval=a.maxval;
                c.maxvalpoz=a.maxvalpoz;
            }
            else
            {
                c.maxval=b.maxval;
                c.maxvalpoz=b.maxvalpoz;
            }
        }
        else
        {
            if (a.maxvalpoz<b.maxvalpoz)
            {
                c.maxval=a.maxval;
                c.maxvalpoz=a.maxvalpoz;
            }
            else
            {
                c.maxval=b.maxval;
                c.maxvalpoz=b.maxvalpoz;
            }
        }
        c.lazy=0;
        return c;
    }
} aint1, aint2;

void calc(int node, int parent)
{
    int mx1,mx2;
    mx1=0;
    mx2=0;
    for (auto x : nodes[node])
    {
        if (x!=parent)
            calc(x,node);
        if (dp[x]>mx1)
        {
            mx2=mx1;
            mx1=dp[x];
        }
        else if (dp[x]>mx2)
        {
            mx2=dp[x];
        }
    }
    dp[node]=1+mx2+(nodes[node].size()-1-2)+1;
}

void dfs(int node, int parent)
{
    for (auto x : nodes[node])
    {
        if (x!=parent)
        {
            p[x]=node;
            depth[x]=depth[node]+1;
            dfs(x,node);
        }
    }
}

void build_path(int l, int r)
{
    int cr,cl,start,en,sofar,pending,len,last,i;
    cr=r;
    cl=l;
    len=0;
    while (depth[r]>depth[l])
    {
        nxt[p[r]]=r;
        r=p[r];
        len++;
    }
    while (depth[l]>depth[r])
    {
        nxt[l]=p[l];
        l=p[l];
        len++;
    }
    while (r!=l)
    {
        nxt[p[r]]=r;
        nxt[l]=p[l];
        l=p[l];
        r=p[r];
        len+=2;
    }
    r=cr;
    l=nxt[cl];
    cnt=0;
    sofar=0;
    last=cl;
    while (l!=r)
    {
        start=cnt;
        en=start;
        pending=0;
        for (auto x : nodes[l])
        {
            if (x!=nxt[l] && x!=last)
            {
                pending++;
                en++;
            }
        }
        sofar+=pending;
        for (auto x : nodes[l])
        {
            if (x!=nxt[l] && x!=last)
            {
                calc(x,l);
                variante[++cnt]=dp[x]+sofar;
                lim[cnt]=len;
                leftie[cnt]=start;
                rightie[cnt]=en;
            }
        }
        last=l;
        l=nxt[l];
        len--;
    }
    start=cnt;
    en=start;
    pending=0;
    for (auto x : nodes[l])
    {
        if (x!=nxt[l] && x!=last)
        {
            pending++;
            en++;
        }
    }
    sofar+=pending;
    for (auto x : nodes[l])
    {
        if (x!=nxt[l] && x!=last)
        {
            calc(x,l);
            variante[++cnt]=dp[x]+sofar;
            lim[cnt]=len;
            leftie[cnt]=start;
            rightie[cnt]=en;
        }
    }
}

signed main()
{
    //ifstream fin("secvp.in");
    //ofstream fout("secvp.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int u,v,i,lbound,rbound;
    Node ans,ans2;
    bool ok;
    cin >> n >> t >> m;
    for (i=1; i<=n-1; i++)
    {
        cin >> u >> v;
        nodes[u].push_back(v);
        nodes[v].push_back(u);
    }
    depth[1]=1;
    dfs(1,-1);
    build_path(t,m);

    aint1.build(0,cnt,1,1);
    aint2.build(0,cnt,1,2);
    ok=true;
    while (ok)
    {
        ans=aint1.query(0,cnt,1,0,cnt);
        if (ans.maxvalpoz==0)
        {
            cout << ans.maxval;
            return 0;
        }
        lbound=leftie[ans.maxvalpoz];
        rbound=rightie[ans.maxvalpoz];
        ans2=aint2.query(0,cnt,1,1,rbound);
        if (ans2.minval==0)
        {
            cout << ans.maxval;
            return 0;
        }
        else
        {
            aint1.disable(0,cnt,1,ans.maxvalpoz);
            aint1.lazy_update(0,cnt,1,0,lbound,1);
            aint2.lazy_update(0,cnt,1,1,rbound,-1);
        }
    }
}

Compilation message

mousetrap.cpp: In function 'void build_path(long long int, long long int)':
mousetrap.cpp:227:47: warning: unused variable 'i' [-Wunused-variable]
  227 |     int cr,cl,start,en,sofar,pending,len,last,i;
      |                                               ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 11 ms 24016 KB Output is correct
6 Correct 10 ms 23924 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 10 ms 23896 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 96728 KB Output is correct
2 Correct 178 ms 89680 KB Output is correct
3 Correct 697 ms 95020 KB Output is correct
4 Correct 236 ms 59616 KB Output is correct
5 Correct 616 ms 95056 KB Output is correct
6 Correct 629 ms 95436 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 11 ms 24016 KB Output is correct
6 Correct 10 ms 23924 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 10 ms 23896 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 11 ms 23812 KB Output is correct
12 Correct 10 ms 23900 KB Output is correct
13 Correct 9 ms 23900 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 10 ms 23980 KB Output is correct
17 Correct 11 ms 23932 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 10 ms 23900 KB Output is correct
20 Correct 10 ms 23900 KB Output is correct
21 Correct 10 ms 23944 KB Output is correct
22 Correct 11 ms 23900 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 10 ms 23896 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 10 ms 23804 KB Output is correct
5 Correct 11 ms 24016 KB Output is correct
6 Correct 10 ms 23924 KB Output is correct
7 Correct 10 ms 23952 KB Output is correct
8 Correct 10 ms 23896 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 197 ms 96728 KB Output is correct
12 Correct 178 ms 89680 KB Output is correct
13 Correct 697 ms 95020 KB Output is correct
14 Correct 236 ms 59616 KB Output is correct
15 Correct 616 ms 95056 KB Output is correct
16 Correct 629 ms 95436 KB Output is correct
17 Correct 11 ms 23812 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 9 ms 23900 KB Output is correct
20 Correct 10 ms 23900 KB Output is correct
21 Correct 10 ms 23900 KB Output is correct
22 Correct 10 ms 23980 KB Output is correct
23 Correct 11 ms 23932 KB Output is correct
24 Correct 10 ms 23900 KB Output is correct
25 Correct 10 ms 23900 KB Output is correct
26 Correct 10 ms 23900 KB Output is correct
27 Correct 10 ms 23944 KB Output is correct
28 Correct 11 ms 23900 KB Output is correct
29 Correct 10 ms 23900 KB Output is correct
30 Correct 200 ms 99852 KB Output is correct
31 Correct 206 ms 99924 KB Output is correct
32 Correct 229 ms 119888 KB Output is correct
33 Correct 227 ms 137300 KB Output is correct
34 Correct 601 ms 98040 KB Output is correct
35 Correct 610 ms 98028 KB Output is correct
36 Correct 589 ms 149076 KB Output is correct
37 Correct 596 ms 149120 KB Output is correct
38 Correct 483 ms 128756 KB Output is correct
39 Correct 468 ms 128852 KB Output is correct
40 Correct 468 ms 128848 KB Output is correct