Submission #1308333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308333		HoriaHaivas	Prize (CEOI22_prize)	C++20	0 / 100	580 ms	82636 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);
}

int p[3][500005];
int h[3][500005];
int pathsum[500005];
int up[19][500005];
vector<int> nodes[3][500005];
bool marked[500005];
queue<int> q;

struct ceva
{
    int unu;
    int doi;
    int trei;
    int patru;
};

ceva query(int a, int b)
{
    int unu,doi,trei,patru;
    cout << "? "  <<  a << " " << b << endl;
    cin >> unu >> doi >> trei >> patru;
    return {unu,doi,trei,patru};
}

void dfs(int node, int parent)
{
    for (auto x : nodes[1][node])
    {
        if (marked[x])
        {
            h[1][x]=h[1][node]+1;
            pathsum[x]=pathsum[node]+query(x,node).unu;
            dfs(x,node);
        }
    }
}

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

int dist(int a, int b)
{
    int c;
    c=lca(a,b);
    return pathsum[a]+pathsum[b]-2*pathsum[c];
}

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,root,a,b,fr,j;
    cin >> n >> k >> qq >> t;
    for (i=1; i<=n; i++)
    {
        cin >> p[1][i];
        if (p[1][i]==-1)
            root=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)
            nodes[2][p[2][i]].push_back(i);
    }
    ///sub1
    q.push(root);
    while (k>0)
    {
        fr=q.front();
        debug(fr);
        marked[fr]=1;
        for (auto x : nodes[1][fr])
        {
            q.push(x);
        }
        k--;
        q.pop();
    }
    for (i=1; i<=n; i++)
    {
        if (marked[i])
            cout << i << " ";
    }
    cout << endl;
    pathsum[root]=0;
    h[1][root]=1;
    dfs(root,-1);
    cout << "!" << endl;
    for (i=1; i<=n; i++)
    {
        up[0][i]=p[1][i];
    }
    for (i=1; i<=18; i++)
    {
        for (j=1; j<=n; j++)
        {
            up[i][j]=up[i-1][up[i-1][j]];
        }
    }
    for (i=1; i<=t; i++)
    {
        cin >> a >> b;
        cout << dist(a,b) << " " << dist(a,b) << endl;
    }
    cout << endl;
    return 0;
}

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