Submission #1095166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095166		HoriaHaivas	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	697 ms	149120 KiB

mousetrap

/*
    "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 (stderr)

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35