Submission #1056520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056520		heeew	Summer Driving (CCO24_day1problem3)	C++14	1 / 25	2862 ms	307072 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=300010;
const int BN=20;

int n,root,m1,m2;
vint edge[MAX_N];
int sz[MAX_N],lock[MAX_N],cp[MAX_N];            //cent data
int dfsi[MAX_N],dfso[MAX_N],dfsr[MAX_N];        //dfs order data
int depth[MAX_N],ac[MAX_N][BN];                 //lca data
vint depv[MAX_N];                               //bfs order data
queue<pii> qc;                                  //queue for cent
int bfso[MAX_N][BN];                            //for cent update
int pa[MAX_N],pi[MAX_N],cc[MAX_N];              //for parent,child calc
int val[MAX_N];vint valc[MAX_N];                //for dt ans
int dseg[MAX_N<<2],lmv[MAX_N];                  //for last move


void dfs_init(int v,int p,int &c)
{
    depth[v]=depth[p]+1;
    ac[v][0]=pa[v]=p;
    for(int i=1;i<BN;i++)
        ac[v][i]=ac[ac[v][i-1]][i-1];
    depv[depth[v]].push_back(c);
    dfsr[c]=v;
    dfsi[v]=c++;
    for(auto v0 : edge[v])
        if(v0!=p)
            pi[v0]=cc[v]++;
    for(auto v0 : edge[v])
        if(v0!=p)
            dfs_init(v0,v,c);
    dfso[v]=c;
}

int lca(int u,int v)
{
    if(depth[u]>depth[v])swap(u,v);
    for(int i=BN-1;i>=0;i--)
        if(depth[ac[v][i]]>=depth[u])
            v=ac[v][i];
    if(v==u)return v;
    for(int i=BN-1;i>=0;i--)
        if(ac[v][i]!=ac[u][i])
        {
            v=ac[v][i];
            u=ac[u][i];
        }
    return ac[v][0];
}
int lcad(int u,int v)
{
    return depth[u]+depth[v]-depth[lca(u,v)]*2;
}
int lcap(int v,int p)
{
    for(int i=BN-1;i>=0;i--)
        if(depth[ac[v][i]]>depth[p])
            v=ac[v][i];
    return v;
}

int fillsz(int v,int p)
{
    sz[v]=1;
    for(auto v0 : edge[v])
        if(v0!=p && !lock[v0])
            sz[v]+=fillsz(v0,v);
    return sz[v];
}

int findct(int v,int p,int h)
{
    for(auto v0 : edge[v])
        if(v0!=p && !lock[v0] && sz[v0]>h)
            return findct(v0,v,h);
    return v;
}

struct Cent
{
    int ct,csz,cd;
    vint vert;
    int md;
    vint dist;
    vint seg;
    void update_(int i,int s,int e,int x,int v)
    {
        if(s>x || e<=x)return;
        if(s==x && x+1==e)
        {
            seg[i]=v;
            return;
        }
        update_(i<<1,s,(s+e)>>1,x,v);
        update_(i<<1|1,(s+e)>>1,e,x,v);
        seg[i]=min(seg[i<<1],seg[i<<1|1]);
    }
    int find_(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return MAX_N;
        if(l<=s && e<=r)return seg[i];
        return min(find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
    }
    void updateout(int x,int v)
    {
        update_(1,0,csz,x,v);
    }
    int findout(int d)
    {
        return find_(1,0,csz,0,dist[min(d,md)]);
    }
    void init_(int ct_,int cd_)
    {
        ct=ct_;cd=cd_;
        fillsz(ct,0);
        csz=sz[ct];
        qc.push({ct,0});
        lock[ct]=2;
        while(!qc.empty())
        {
            pii p=qc.front();qc.pop();
            bfso[p.first][cd]=vert.size();
            vert.push_back(p.first);
            if(dist.size()<=p.second)dist.push_back(1);
            else dist[p.second]++;
            for(auto v : edge[p.first])
                if(!lock[v])
                {
                    lock[v]=2;
                    qc.push({v,p.second+1});
                }
        }
        for(auto v : vert)lock[v]=0;
        md=dist.size()-1;
        for(int i=0;i<md;i++)dist[i+1]+=dist[i];
        seg.resize(csz<<2);
    }
};
Cent cent[MAX_N];

void cent_init(int v,int p,int d)
{
    v=findct(v,0,fillsz(v,0)/2);
    cp[v]=p;
    cent[v].init_(v,d);
    lock[v]=1;
    for(auto v0 : edge[v])
        if(!lock[v0])
            cent_init(v0,v,d+1);
}

void updatein(int v,int vv)
{
    int ct=v;
    while(ct)
    {
        cent[ct].updateout(bfso[v][cent[ct].cd],vv);
        ct=cp[ct];
    }
}

int findin(int v,int d)
{
    int ret=MAX_N;
    int ct=v;
    while(ct)
    {
        int d2=d-lcad(v,ct);
        if(d2>=0)
            ret=min(ret,cent[ct].findout(d2));
        ct=cp[ct];
    }
    return ret;
}

void updated(int i,int s,int e,int x,int v)
{
    if(s>x || e<=x)return;
    if(s==x && x+1==e)
    {
        dseg[i]=v;
        return;
    }
    updated(i<<1,s,(s+e)>>1,x,v);
    updated(i<<1|1,(s+e)>>1,e,x,v);
    dseg[i]=min(dseg[i<<1],dseg[i<<1|1]);
}

int findd(int i,int s,int e,int l,int r)
{
    if(s>=r || e<=l)return MAX_N;
    if(l<=s && e<=r)return dseg[i];
    return min(findd(i<<1,s,(s+e)>>1,l,r),findd(i<<1|1,(s+e)>>1,e,l,r));
}

void lastmove_init()
{
    for(int i=0;i<n;i++)
        updated(1,0,n,i,MAX_N);
    for(int d=MAX_N-1;d>=1;d--)
    {
        for(auto i : depv[d])
        {
            int v=dfsr[i];
            updated(1,0,n,i,v);
            lmv[v]=findd(1,0,n,dfsi[v],dfso[v]);
        }
        if(d+m2>=MAX_N)continue;
        for(auto i : depv[d+m2])
            updated(1,0,n,i,MAX_N);
    }
}

void calc(int v)
{
    int d=depth[v],d2=depth[v]+m1,li,ri;
    if(d2>=MAX_N)
        li=ri=0;
    else
    {
        li=lower_bound(depv[d2].begin(),depv[d2].end(),dfsi[v])-depv[d2].begin();
        ri=lower_bound(depv[d2].begin(),depv[d2].end(),dfso[v])-depv[d2].begin();
    }
    vint ov(cc[v],-1);
    for(int i=li;i<ri;i++)
    {
        int c=dfsr[depv[d2][i]];
        int v0=lcap(c,v);
        ov[pi[v0]]=max(ov[pi[v0]],findin(c,m2));
        if(i!=ri-1)
        {
            int c2=dfsr[depv[d2][i+1]];
            int l=lca(c,c2);
            if(l!=v)
                updatein(l,valc[l][pi[lcap(c2,l)]]);
        }
    }
    for(int i=ri-2;i>=li;i--)
    {
        int c=dfsr[depv[d2][i]];
        int c2=dfsr[depv[d2][i+1]];
        int l=lca(c,c2);
        if(l!=v)
            updatein(l,valc[l][pi[lcap(c,l)]]);
    }
    int pv=-1,plm=v;
    vint lv(cc[v],-1),rv(cc[v],-1);
    vint olm(cc[v],MAX_N);
    vint llm(cc[v],MAX_N),rlm(cc[v],MAX_N);
    for(auto v0 : edge[v])
        if(v0!=pa[v])
            olm[pi[v0]]=lmv[v0];
    for(int i=0;i<cc[v];i++)
    {
        pv=max(pv,ov[i]);
        plm=min(plm,olm[i]);
    }
    for(int i=0;i<cc[v]-1;i++)
    {
        lv[i+1]=max(lv[i],ov[i]);
        llm[i+1]=min(llm[i],olm[i]);
    }
    for(int i=cc[v]-1;i>=1;i--)
    {
        rv[i-1]=max(rv[i],ov[i]);
        rlm[i-1]=min(rlm[i],olm[i]);
    }
    if(pv==-1)pv=plm;
    val[v]=pv;
    valc[v].resize(cc[v]);
    for(int i=0;i<cc[v];i++)
    {
        int cv=max(lv[i],rv[i]);
        if(cv==-1)cv=min(v,min(llm[i],rlm[i]));
        valc[v][i]=cv;
    }
}

void solve()
{
    for(int d=MAX_N-1;d>=1;d--)
    {
        for(auto i : depv[d])
        {
            int v=dfsr[i];
            calc(v);
            if(valc[v].empty())updatein(v,val[v]);
            else updatein(v,valc[v][0]);
        }
        if(d+m1-1>=MAX_N)continue;
        for(auto i : depv[d+m1-1])
        {
            int v=dfsr[i];
            updatein(v,val[v]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> root >> m1 >> m2;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    if(m1<=m2)
    {
        cout << 1;
        return 0;
    }
    int idx=0;
    dfs_init(root,0,idx);
    cent_init(root,0,0);
    lastmove_init();
    solve();
    cout << val[root];
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void Cent::init_(int, int)':
Main.cpp:134:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |             if(dist.size()<=p.second)dist.push_back(1);
      |                ~~~~~~~~~~~^~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:226:9: warning: unused variable 'd' [-Wunused-variable]
  226 |     int d=depth[v],d2=depth[v]+m1,li,ri;
      |         ^

• Subtask 1: 1 / 1
• Subtask 2: 0 / 4
• Subtask 3: 0 / 5
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 6
• Subtask 7: 0 / 2