제출 #1308401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308401		simona1230	Prize (CEOI22_prize)	C++20	0 / 100	1387 ms	1114112 KiB

Main

#include <bits/stdc++.h>

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

int r[2];
vector<int> v[4][maxn];
vector<int> g[4][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 dep[maxn];
int mark[maxn];

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

    if(pr!=-1)dep[i]=dep[pr]+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[4][maxn],in[2][maxn];
int op[2][maxn];
int id[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;
        dfsl(nb,i,s);
        e[s].push_back(in[s][i]);
    }
}

int minn[2][2*maxn][32];
int lh[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<=25;j++)
    {
        for(int i=0;i<e[s].size();i++)
        {
            if(i+(1<<(j-1))<maxn)
            minn[s][i][j]=min(minn[s][i][j-1],minn[s][i+(1<<(j-1))][j-1]);
        }
    }

    for(int i=2;i<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[4][maxn];
void die(int i,int pr,int s)
{
    //cout<<"!?!? "<<s<<" "<<i<<endl;
    u[s][i]=1;
    for(int j=0;j<v[s][i].size();j++)
    {
        int nb=v[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);
	mark[p[k-1]]=0;
	mark[r[1]]=1;
	p.pop_back();
	p.push_back(r[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);
    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;
        v[2][x].push_back(y);
        g[2][x].push_back(b-a);
        v[2][y].push_back(x);
        g[2][y].push_back(a-b);

        v[3][x].push_back(h1);
        g[3][x].push_back(-c);
        v[3][h1].push_back(x);
        g[3][h1].push_back(c);

        v[3][y].push_back(h1);
        g[3][y].push_back(-d);
        v[3][h1].push_back(y);
        g[3][h1].push_back(d);
        // 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;


    }

    die(r[0],-1,2);
    die(r[1],-1,3);
    /*for(int i=1;i<=n;i++)
    {
        cout<<w[3][i]<<" "<<i<<": ";
        for(int j=0;j<v[3][i].size();j++)
            cout<<v[3][i][j]<<" "<<g[3][i][j]<<" / ";
        cout<<endl;
    }*/

    /*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[2][i]=w[2][x]+w[2][y]-2*w[2][h0];
        ans[3][i]=w[3][x]+w[3][y]-2*w[3][h1];
    }

    for(int i=0;i<t;i++)
        cout<<ans[2][i]<<" "<<ans[3][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

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: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24