oj.uz

Submission #292847

# Submission time Handle Problem Language Result Execution time Memory
292847 2020-09-07T14:11:57 Z 최은수(#5797) ROI16_sending (ROI16_sending) C++17
12 / 100
 458 ms 57488 KB 
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e8+7;
const ll INF=1e18;
const int mx=200010;
int dep[mx];
int spa[mx][18];
inline int kpa(int x,int k)
{
    for(;k>0;k^=k&-k)
        x=spa[x][__builtin_ctz(k)];
    return x;
}
inline int lca(int x,int y)
{
    if(dep[x]>dep[y])
        x=kpa(x,dep[x]-dep[y]);
    else
        y=kpa(y,dep[y]-dep[x]);
    if(x==y)
        return x;
    for(int i=18;i-->0;)
        if(spa[x][i]!=spa[y][i])
            x=spa[x][i],y=spa[y][i];
    return spa[x][0];
}
vector<int>adj[mx];
int inord[mx],outord[mx];
int ordct;
void dfs(int x,int p)
{
    inord[x]=++ordct;
    dep[x]=dep[spa[x][0]=p]+1;
    for(int i=0;i<17;i++)
        spa[x][i+1]=spa[spa[x][i]][i];
    for(int&t:adj[x])
        dfs(t,x);
    outord[x]=ordct;
    return;
}
map<int,vector<int> >mp[mx];
vector<int>vv[mx];
pi qry[mx];
int lc[mx];
int ansv=0,ansi=1,ansj=2;
pi mn1[mx],mn2[mx];
inline void upd(int x,pi v)
{
    if(v<mn1[x])
        mn2[x]=mn1[x],mn1[x]=v;
    else if(v<mn2[x])
        mn2[x]=v;
    return;
}
void dfs2(int x)
{
    mn1[x]=pi(inf,0);
    mn2[x]=pi(inf,0);
    for(int&t:vv[x])
        upd(x,pi(dep[lc[t]],t));
    for(int&t:adj[x])
        dfs2(t),upd(x,mn1[t]),upd(x,mn2[t]);
    if(dep[x]-mn2[x].fi>ansv)
        ansv=dep[x]-mn2[x].fi,ansi=mn1[x].se,ansj=mn2[x].se;
    return;
}
vector<pi>adj2[mx];
bool chk[mx];
int siz[mx];
void cdfs0(int x,int p)
{
    siz[x]=1;
    for(pi&t:adj2[x])
        if(t.fi!=p)
            cdfs0(t.fi,x),siz[x]+=siz[t.fi];
    return;
}
int cdis[mx][18];
void cdfs(int x,int p,int d,int cd,vector<int>&v,bool push=0)
{
    if(push)
        v.eb(x);
    cdis[x][cd]=d;
    siz[x]=1;
    for(pi&t:adj2[x])
        if(!chk[t.fi]&&t.fi!=p)
            cdfs(t.fi,x,d+t.se,cd,v,push),siz[x]+=siz[t.fi];
    return;
}
int cent(int x,int p,int sz)
{
    int ms=-1,mi=-1;
    for(pi&t:adj2[x])
        if(!chk[t.fi]&&t.fi!=p&&siz[t.fi]>ms)
            ms=siz[t.fi],mi=t.fi;
    if(ms<=sz)
        return x;
    return cent(mi,x,sz);
}
int cpa[mx],cdep[mx];
void dnc(int x,bool push=0)
{
    chk[x]=1;
    if(push)
        vv[x].eb(x);
    for(pi&t:adj2[x])
    {
        if(chk[t.fi])
            continue;
        cdfs(t.fi,x,t.se,cdep[x],vv[x],push);
        int nc=cent(t.fi,x,siz[t.fi]/2);
        cpa[nc]=x;
        cdep[nc]=cdep[x]+1;
        dnc(nc,push);
    }
    return;
}
vector<int>vert[mx];
pi mxv[mx];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    for(int i=1;i++<n;)
    {
        int p;
        cin>>p;
        adj[p].eb(i);
    }
    dfs(1,0);
    for(int i=0;i++<k;)
    {
        cin>>qry[i].fi>>qry[i].se;
        const int&l=lc[i]=lca(qry[i].fi,qry[i].se);
        if(qry[i].fi!=l&&qry[i].se!=l)
        {
            int l1=kpa(qry[i].fi,dep[qry[i].fi]-dep[l]-1);
            int l2=kpa(qry[i].se,dep[qry[i].se]-dep[l]-1);
            if(l1>l2)
                swap(l1,l2),swap(qry[i].fi,qry[i].se);
            mp[l1][l2].eb(i);
        }
        if(qry[i].fi!=l)
            vv[qry[i].fi].eb(i);
        if(qry[i].se!=l)
            vv[qry[i].se].eb(i);
    }
    dfs2(1);
    auto cmp=[&](const int&x,const int&y)->bool{return inord[x]<inord[y];};
    for(int i=0;i++<n;)
        adj[i].clear(),vv[i].clear();
    for(int i=0;i++<n;)
    {
        const int rt=spa[i][0];
        for(const auto&tv:mp[i])
        {
            if((int)tv.se.size()<2)
                continue;
            const vector<int>&v=tv.se;
            vector<int>v1,v2;
            for(const int&t:v)
                v1.eb(qry[t].fi),v2.eb(qry[t].se);
            sort(all(v1),cmp);
            {
                int n=v1.size();
                for(int i=1;i<n;i++)
                    v1.eb(lca(v1[i-1],v1[i]));
                sort(all(v1),cmp);
                v1.erase(unique(all(v1)),v1.end());
                vector<int>stk;
                for(int&t:v1)
                {
                    while(!stk.empty()&&outord[stk.back()]<inord[t])
                        stk.pop_back();
                    if(!stk.empty())
                    {
                        int u=stk.back();
                        int w=dep[t]-dep[u];
                        adj2[t].eb(u,w);
                        adj2[u].eb(t,w);
                    }
                    stk.eb(t);
                }
            }
            sort(all(v2),cmp);
            {
                int n=v2.size();
                for(int i=1;i<n;i++)
                    v2.eb(lca(v2[i-1],v2[i]));
                sort(all(v2),cmp);
                v2.erase(unique(all(v2)),v2.end());
                vector<int>stk;
                for(int&t:v2)
                {
                    while(!stk.empty()&&outord[stk.back()]<inord[t])
                        stk.pop_back();
                    if(!stk.empty())
                    {
                        int u=stk.back();
                        int w=dep[t]-dep[u];
                        adj2[t].eb(u,w);
                        adj2[u].eb(t,w);
                    }
                    stk.eb(t);
                }
            }
            {
                cdfs0(v1[0],0);
                int cc=cent(v1[0],0,siz[v1[0]]/2);
                cdep[cc]=cpa[cc]=0;
                dnc(cc,1);
            }
            {
                cdfs0(v2[0],0);
                int cc=cent(v2[0],0,siz[v2[0]]/2);
                cdep[cc]=cpa[cc]=0;
                dnc(cc,1);
            }
            for(int&t:v2)
                mxv[t].fi=-inf;
            for(const int&t:v)
                vert[qry[t].fi].eb(t);
            for(int&u0:v1)
            {
                int cd1=cdep[u0];
                for(int&vvv:vv[u0])
                {
                    for(int&vv0:vert[vvv])
                    {
                        int u1=qry[vv0].fi;
                        int u2=qry[vv0].se;
                        int cur=u2;
                        while(cur>0)
                        {
                            int part=dep[u1]+dep[u2]-2*dep[rt]-cdis[u1][cd1]
                            -cdis[u2][cdep[cur]];
                            if((part+mxv[cur].fi)/2>ansv)
                                ansv=(part+mxv[cur].fi)/2,ansi=vv0,ansj=mxv[cur].se;
                            mxv[cur]=max(mxv[cur],pi(part,vv0));
                            cur=cpa[cur];
                        }
                    }
                }
                for(int&vvv:vv[u0])
                    for(int&vv0:vert[vvv])
                        for(int cur=qry[vv0].se;cur>0;cur=cpa[cur])
                            mxv[cur].fi=-inf;
            }
            for(int&t:v1)
                adj2[t].clear(),vv[t].clear(),vert[t].clear(),chk[t]=0;
            for(int&t:v2)
                adj2[t].clear(),chk[t]=0;
        }
    }
    cout<<ansv<<endl;
    cout<<ansi<<' '<<ansj<<endl;
    return 0;
}

Subtask #1
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 57416 KB Output is correct
2 Incorrect 458 ms 57488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 41848 KB Output is correct
2 Correct 130 ms 41968 KB Output is correct
3 Correct 111 ms 47992 KB Output is correct
4 Correct 114 ms 45688 KB Output is correct
5 Correct 120 ms 44044 KB Output is correct
6 Correct 68 ms 40548 KB Output is correct
7 Correct 112 ms 48092 KB Output is correct
8 Correct 67 ms 40804 KB Output is correct
9 Correct 84 ms 41752 KB Output is correct
10 Correct 69 ms 47092 KB Output is correct
11 Correct 69 ms 47224 KB Output is correct
12 Correct 74 ms 47228 KB Output is correct
13 Correct 113 ms 47992 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28544 KB Output is correct
6 Correct 20 ms 28672 KB Output is correct
7 Incorrect 21 ms 28648 KB Output isn't correct
8 Halted 0 ms 0 KB -