제출 #1308460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308460		aaa111	Prize (CEOI22_prize)	C++20	100 / 100	2521 ms	761328 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn=1000000+5;

int r[2];
vector<int> v[2][maxn];
vector<int> f[2][maxn],g[2][maxn];
int n,k,q,t;

void read()
{
    cin>>n>>k>>q>>t;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==-1)r[0]=i;
        else v[0][x].push_back(i);
    }

    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x==-1)r[1]=i;
        else
        {
            v[1][x].push_back(i);
            v[1][i].push_back(x);
        }
    }
}

int cnt=0;
vector<int> p;
int mark[maxn];

void dfsp(int i,int pr)
{
    if(cnt==k)return;
    cnt++;
    p.push_back(i);
    mark[i]=1;

    for(int j=0;j<v[0][i].size();j++)
    {
        int nb=v[0][i][j];
        dfsp(nb,i);
    }
}

vector<pair<int,int> > qr;

int ans[2][maxn];
vector<int> e[2];
int num[2]={1,1};
int w[2][maxn],in[2][maxn];
int op[2][maxn];
int id[2][maxn];
int dep[2][maxn];

void dfsl(int i,int pr,int s)
{
    op[s][num[s]]=i;
    in[s][i]=num[s]++;
    id[s][i]=e[s].size();
    e[s].push_back(in[s][i]);

    for(int j=0;j<v[s][i].size();j++)
    {
        int nb=v[s][i][j];
        if(nb==pr)continue;
        dep[s][nb]=dep[s][i]+1;
        dfsl(nb,i,s);
        e[s].push_back(in[s][i]);
    }
}

int minn[2][2*maxn][22];
int lh[2*maxn];

void prec()
{
    for(int s=0;s<=1;s++)
    for(int i=0;i<e[s].size();i++)
        minn[s][i][0]=e[s][i];

    for(int s=0;s<=1;s++)
    for(int j=1;j<=21;j++)
    {
        for(int i=0;i<e[s].size();i++)
        {
            if(i+(1<<(j-1))<2*maxn)
            minn[s][i][j]=min(minn[s][i][j-1],minn[s][i+(1<<(j-1))][j-1]);
        }
    }

    for(int i=2;i<2*maxn;i++)
        lh[i]=lh[i/2]+1;
}


int lca(int x,int y,int s)
{
    //cout<<x<<" - "<<y<<endl;
    x=id[s][x];
    y=id[s][y];

    if(x>y)swap(x,y);
    int len=y-x+1;
    len=lh[len];

    //cout<<x<<" "<<y<<endl;
    int hehe=op[s][min(minn[s][x][len],minn[s][y-(1<<len)+1][len])];
    //cout<<"! "<<endl;
    return hehe;
}

int last;
void dfsq(int i,int pr)
{
    if(mark[i])
    {
        if(last)qr.push_back({last,i});
        last=i;
    }

    for(int j=0;j<v[1][i].size();j++)
    {
        int nb=v[1][i][j];
        if(nb==pr)continue;

        dfsq(nb,i);
    }
}

int u[2][maxn];
void die(int i,int pr,int s)
{
    //cout<<"!?!? "<<s<<" "<<i<<endl;
    u[s][i]=1;
    for(int j=0;j<f[s][i].size();j++)
    {
        int nb=f[s][i][j];
        if(u[s][nb])continue;
        w[s][nb]=w[s][i]+g[s][i][j];
        //cout<<"w "<<s<<" "<<nb<<" "<<w[s][nb]<<endl;
        die(nb,i,s);
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	dfsp(r[0],-1);

	for(int i=0;i<p.size();i++)
        cout<<p[i]<<" ";
    cout<<endl;
    cout.flush();

    dfsq(r[1],-1);

    for(int i=0;i<qr.size();i++)
    {
        cout<<"? "<<qr[i].first<<" "<<qr[i].second<<endl;
    }
    cout<<"!"<<endl;
    cout.flush();

    dfsl(r[0],-1,0);
    dfsl(r[1],-1,1);
    r[1]=p[0];
    prec();

    for(int i=0;i<qr.size();i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int x=qr[i].first,y=qr[i].second;
        int h0=lca(x,y,0),h1=lca(x,y,1);
        //cout<<x<<" "<<h1<<" "<<c<<endl;
        //cout<<y<<" "<<h1<<" "<<d<<endl;
        f[0][x].push_back(y);
        g[0][x].push_back(b-a);
        f[0][y].push_back(x);
        g[0][y].push_back(a-b);

        f[1][x].push_back(h1);
        g[1][x].push_back(-c);
        f[1][h1].push_back(x);
        g[1][h1].push_back(c);

        f[1][y].push_back(h1);
        g[1][y].push_back(-d);
        f[1][h1].push_back(y);
        g[1][h1].push_back(d);
        //cout<<"+ "<<h1<<endl;
        if(dep[1][x]<dep[1][r[1]])
            r[1]=x;
        if(dep[1][y]<dep[1][r[1]])
            r[1]=y;
        if(dep[1][h1]<dep[1][r[1]])
            r[1]=h1;
        // w[0][x]-w[0][h0]=a
        // w[0][y]-w[0][h0]=b;

        // w[1][x]-w[1][h1]=c
        // w[1][y]-w[1][h1]=d;


    }
    //cout<<r[1]<<endl;

    /*for(int i=1;i<=n;i++)
    {
        cout<<w[1][i]<<" "<<i<<": ";
        for(int j=0;j<f[1][i].size();j++)
            cout<<f[1][i][j]<<" "<<g[1][i][j]<<" / ";
        cout<<endl;
    }*/

    die(r[0],-1,0);
    die(r[1],-1,1);


    /*for(int i=1;i<=n;i++)
        for(int j=0;j<=3;j++)
            cout<<i<<" -- "<<j<<" "<<jump[2][i][j]<<" "<<jump[3][i][j]<<endl;*/

    for(int i=0;i<t;i++)
    {
        int x,y;
        cin>>x>>y;
        int h0=lca(x,y,0),h1=lca(x,y,1);

        //cout<<h0<<" + "<<h1<<endl;
        ans[0][i]=w[0][x]+w[0][y]-2*w[0][h0];
        ans[1][i]=w[1][x]+w[1][y]-2*w[1][h1];
    }

    for(int i=0;i<t;i++)
        cout<<ans[0][i]<<" "<<ans[1][i]<<endl;
    cout.flush();

	return 0;
}

/*
9 6 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7

3 2 0 3
2 12 0 12
5 0 12 9
10 0 0 1
0 3 13 5
1 7
8 5
2 4

9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7

6 0 0 13
0 3 13 5
1 2
2 7
1 7
*/

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24