Submission #1309156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309156		HoriaHaivas	Prize (CEOI22_prize)	C++20	10 / 100	2118 ms	623220 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct muchie
{
    int to;
    int cost;
};

int p[3][1000005];
int h[3][1000005];
int ans[3][1000005];
int up[3][21][1000005];
vector<int> nodes[3][1000005];
vector<muchie> new_nodes[3][1000005];
int tin[3][1000005];
int revstamp[3][1000005];
int tout[3][1000005];
bool marked[1000005];
bool visited[3][1000005];
int pathsum[3][1000005];
vector<pair<int,int>> v;
vector<int> v2;
int timer;

bool cmp(int a, int b)
{
    return tin[2][a]<tin[2][b];
}


void query(int a, int b)
{
    cout << "? " << a << " " << b << endl;
}

void dfs(int tree, int node, int parent)
{
    timer++;
    tin[tree][node]=timer;
    revstamp[tree][timer]=node;
    for (auto x : nodes[tree][node])
    {
        h[tree][x]=h[tree][node]+1;
        dfs(tree,x,node);
    }
    tout[tree][node]=timer;
}

int lca(int tree, int a, int b)
{
    int k,i;
    if (h[tree][a]<h[tree][b])
        swap(a,b);
    k=h[tree][a]-h[tree][b];
    for (i=20; i>=0; i--)
    {
        if (k&(1<<i))
            a=up[tree][i][a];
    }
    if (a==b)
        return a;
    for (i=20; i>=0; i--)
    {
        if (up[tree][i][a]!=up[tree][i][b])
        {
            a=up[tree][i][a];
            b=up[tree][i][b];
        }
    }
    return up[tree][0][a];
}

void dfs2(int tree, int node)
{
    if (visited[tree][node])
        return;
    visited[tree][node]=1;
    for (auto x : new_nodes[tree][node])
    {
        if (!visited[tree][x.to])
        {
            pathsum[tree][x.to]=pathsum[tree][node]+x.cost;
            dfs2(tree,x.to);
        }
    }
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ///ios_base::sync_with_stdio(0);
    ///cin.tie(0);
    ///cout.tie(0);
    int n,k,qq,t,i,root1,root2,a,b,fr,j,c,d,elcea1,elcea2,mx1,mx2,special_node1,special_node2,val1,val2;
    cin >> n >> k >> qq >> t;
    for (i=1; i<=n; i++)
    {
        cin >> p[1][i];
        if (p[1][i]==-1)
            root1=i;
        else
            nodes[1][p[1][i]].push_back(i);
    }
    for (i=1; i<=n; i++)
    {
        cin >> p[2][i];
        if (p[2][i]==-1)
            root2=i;
        else
            nodes[2][p[2][i]].push_back(i);
    }
    h[1][root1]=1;
    timer=0;
    dfs(1,root1,-1);
    h[2][root2]=1;
    timer=0;
    dfs(2,root2,-1);
    for (i=1; i<=n; i++)
    {
        up[1][0][i]=p[1][i];
        up[2][0][i]=p[2][i];
    }
    for (i=1; i<=20; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (up[1][i-1][j]!=-1)
                up[1][i][j]=up[1][i-1][up[1][i-1][j]];
            else
                up[1][i][j]=-1;
            if (up[2][i-1][j]!=-1)
                up[2][i][j]=up[2][i-1][up[2][i-1][j]];
            else
                up[2][i][j]=-1;
        }
    }
    for (i=1; i<=k; i++)
    {
        marked[revstamp[1][i]]=1;
        v2.push_back(revstamp[1][i]);
        cout << revstamp[1][i] << " ";
    }
    cout << endl;
    cout.flush();
    sort(v2.begin(),v2.end(),cmp);
    for (i=0; i<v2.size()-1; i++)
    {
        query(v2[i],v2[i+1]);
        v.push_back({v2[i],v2[i+1]});
    }
    cout << "!" << endl;
    cout.flush();
    mx1=0;
    mx2=0;
    h[1][mx1]=1e9;
    h[2][mx2]=1e9;
    for (i=0; i<v.size(); i++)
    {
        cin >> a >> b >> c >> d;
        new_nodes[1][v[i].first].push_back({v[i].second,b-a});
        new_nodes[1][v[i].second].push_back({v[i].first,a-b});
        new_nodes[2][v[i].first].push_back({v[i].second,d-c});
        new_nodes[2][v[i].second].push_back({v[i].first,c-d});
        elcea1=lca(1,v[i].first,v[i].second);
        elcea2=lca(2,v[i].first,v[i].second);
        if (h[1][elcea1]<h[1][mx1])
        {
            mx1=elcea1;
            special_node1=v[i].first;
            val1=a;
        }
        if (h[2][elcea2]<h[2][mx2])
        {
            mx2=elcea2;
            special_node2=v[i].first;
            val2=c;
        }
    }
    new_nodes[1][mx1].push_back({special_node1,val1});
    new_nodes[2][mx2].push_back({special_node2,val2});
    pathsum[1][mx1]=0;
    dfs2(1,mx1);
    pathsum[2][mx2]=0;
    dfs2(2,mx2);
    for (i=1; i<=t; i++)
    {
        cin >> a >> b;
        c=lca(1,a,b);
        ans[1][i]=pathsum[1][a]+pathsum[1][b]-2*pathsum[1][c];
        c=lca(2,a,b);
        ans[2][i]=pathsum[2][a]+pathsum[2][b]-2*pathsum[2][c];
    }
    for (i=1; i<=t; i++)
    {
        cout << ans[1][i] << " " << ans[2][i] << endl;
    }
    cout << 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