oj.uz

답안 #653210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653210 2022-10-26T08:07:55 Z Rafi22 Prize (CEOI22_prize) C++14
10 / 100
 2040 ms 489104 KB 
#include <bits/stdc++.h>

using namespace std;

//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=1000007;

vector<int>G1[N],G2[N],G3[N];
int d1[N],d2[N];
bool odw[N];
vector<pair<int,int>>X[N],X1[N];
bool is[N];
int n,k,q,t;

int skok[N][20];
int pre[N];
int post[N];
int c=0;

void dfs(int v,int o)
{
    pre[v]=++c;
    skok[v][0]=o;
    for(int i=1;i<20;i++) skok[v][i]=skok[skok[v][i-1]][i-1];
    if(k>0)
    {
        cout<<v<<" ";
        is[v]=1;
        k--;
    }
    for(auto u:G1[v]) dfs(u,v);
    post[v]=++c;
}

int lca(int u,int v)
{
    if(pre[u]<=pre[v]&&post[u]>=post[v]) return u;
    if(pre[v]<=pre[u]&&post[v]>=post[u]) return v;
    for(int i=19;i>=0;i--) if(!(pre[skok[u][i]]<=pre[v]&&post[skok[u][i]]>=post[v])) u=skok[u][i];
    return skok[u][0];
}

vector<pair<pair<int,int>,int>>xd;

void qry(int u,int v,int x)
{
    if(!is[u]||!is[v]) for(int i=0;i<1000000000;i++) dfs(1,0);
    cout<<"? "<<u<<" "<<v<<endl;
    xd.pb({{u,v},x});
}

int last[N];
int last1[N];

int pre1[N];
int post1[N];

void dfs1(int v)
{
    pre1[v]=c++;
    int l=0,l1=0,cc=0;
    for(auto u:G2[v])
    {
        dfs1(u);
        if(last[u]>0)
        {
            c++;
            if(is[v])
            {
                G3[v].pb(last1[u]);
                qry(last[u],v,v);
            }
            else if(cc>1)
            {
                if(cc==2) G3[v].pb(l1);
                G3[v].pb(last1[u]);
                qry(l,last[u],v);
            }
            else
            {
                l=last[u];
                l1=last1[u];
            }
        }
    }
    if(is[v]) last[v]=v;
    else last[v]=l;
    if(is[v]||cc>1) last1[v]=v;
    else last1[v]=l1;
    post1[v]=c++;
}

int skok1[N][20];


void dfs2(int v,int o)
{
    pre1[v]=c++;
    skok1[v][0]=o;
    for(int i=1;i<20;i++) skok1[v][i]=skok1[skok1[v][i-1]][i-1];
    for(auto u:G3[v]) dfs2(u,v);
    post1[v]=c++;
}

int lca1(int u,int v)
{
    if(pre1[u]<=pre1[v]&&post1[u]>=post1[v]) return u;
    if(pre1[v]<=pre1[u]&&post1[v]>=post1[u]) return v;
    for(int i=19;i>=0;i--) if(!(pre1[skok1[u][i]]<=pre1[v]&&post1[skok1[u][i]]>=post1[v])) u=skok1[u][i];
    return skok1[u][0];
}

int U[N],V[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k>>q>>t;
    int K=k;
    int r1,r2,p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) r1=i;
        else G1[p].pb(i);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>p;
        if(p==-1) r2=i;
        else G2[p].pb(i);
    }
    dfs(r1,r1);
    cout<<endl;
    c=0;
    dfs1(r2);
    if(sz(xd)>K)
    {
        return 2137;
      //  for(int i=0;i<100000000;i++) dfs(1,0);
    }
    cout<<"!"<<endl;
    for(auto c:xd)
    {
        int u=c.st.st,v=c.st.nd,x=c.nd;
        int d1,d2,d3,d4;
        cin>>d1>>d2>>d3>>d4;
        int l=lca(u,v);
        X[l].pb({u,d1});
        X[u].pb({l,d1});
        X[l].pb({v,d2});
        X[v].pb({l,d2});
        X1[x].pb({u,d3});
        X1[u].pb({x,d3});
        X1[x].pb({v,d4});
        X1[v].pb({x,d4});
    }
    c=0;
    dfs2(last1[r2],last1[r2]);
    deque<int>Q;
    Q.pb(r1);
    odw[r1]=1;
    while(sz(Q)>0)
    {
        int v=Q[0];
        Q.pop_front();
        for(auto x:X[v])
        {
            if(odw[x.st]) continue;
            odw[x.st]=1;
            Q.pb(x.st);
            if(pre[x.st]>=pre[v]) d1[x.st]=d1[v]+x.nd;
            else d1[x.st]=d1[v]-x.nd;
        }
    }
    memset(odw,0,sizeof odw);
    Q.pb(r2);
    odw[r2]=1;
    while(sz(Q)>0)
    {
        int v=Q[0];
        Q.pop_front();
        for(auto x:X1[v])
        {
            if(odw[x.st]) continue;
            odw[x.st]=1;
            Q.pb(x.st);
            if(pre1[x.st]>=pre1[v]) d2[x.st]=d2[v]+x.nd;
            else d2[x.st]=d2[v]-x.nd;
        }
    }
    for(int i=1;i<=t;i++) cin>>U[i]>>V[i];
    for(int i=1;i<=t;i++)
    {
        int u=U[i],v=V[i];
        int l=lca(u,v);
        cout<<d1[u]+d1[v]-2*d1[l]<<" ";
        l=lca1(u,v);
        cout<<d2[u]+d2[v]-2*d2[l]<<endl;
    }


    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1185 ms 308960 KB Output is correct
2 Correct 1180 ms 312720 KB Output is correct
3 Correct 982 ms 240000 KB Output is correct
4 Correct 950 ms 239312 KB Output is correct
5 Correct 958 ms 242728 KB Output is correct
6 Correct 1294 ms 255484 KB Output is correct
7 Correct 1265 ms 255220 KB Output is correct
8 Correct 1248 ms 254344 KB Output is correct
9 Correct 967 ms 239736 KB Output is correct
10 Correct 1211 ms 241968 KB Output is correct
11 Correct 1020 ms 237864 KB Output is correct
12 Correct 1002 ms 241504 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1079 ms 310836 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 795 ms 258164 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1610 ms 401312 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2040 ms 489104 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -