Submission #1308052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308052		simona1230	Prize (CEOI22_prize)	C++20	10 / 100	477 ms	186232 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+5;

int r[2];
vector<int> v[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);
    }
}

int cnt=0;
vector<int> p;
vector<pair<int,int> > v2[maxn];
vector<pair<int,int> > qr;

void dfsp(int i,int pr)
{
    if(cnt==k)return;
    cnt++;
    p.push_back(i);
    if(pr!=-1)qr.push_back({pr,i});

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

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

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

    for(int j=0;j<v2[i].size();j++)
    {
        int nb=v2[i][j].first;
        if(nb==p)continue;
        w[nb]=w[i]+v2[i][j].second;
        dfs2(nb,i);
        e.push_back(in[i]);
    }
}

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

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

    for(int j=1;j<=25;j++)
    {
        for(int i=0;i<e.size();i++)
        {
            if(i+(1<<(j-1))<maxn)
            minn[i][j]=min(minn[i][j-1],minn[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)
{
    x=id[x];
    y=id[y];

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

    return op[min(minn[x][len],minn[y-(1<<len)+1][len])];
}

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();

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

    for(int i=0;i<qr.size();i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int x=max(a,b);
        v2[qr[i].first].push_back({qr[i].second,x});
        v2[qr[i].second].push_back({qr[i].first,x});
    }

    dfs2(r[0],-1);
    prec();

    for(int i=0;i<t;i++)
    {
        int x,y;
        cin>>x>>y;
        int h=lca(x,y);
        ans[i]={w[x]+w[y]-2*w[h]};
        //cout<<h<<"?!?!"<<endl;
    }

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

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