Submission #1094871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094871		MateiKing80	Prize (CEOI22_prize)	C++14	100 / 100	2397 ms	551296 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 1e6 + 5;
vector<int> fii[2][N];
int ti[2][N], to[2][N], lift[2][N][20];
int dist[2][N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k, q, T;
    cin >> n >> k >> q >> T;
    int R[2] {};
    for(int i = 1; i <= n; i ++)
    {
        int p;
        cin >> p;
        if(~p)
            fii[0][p].push_back(i);
        else
            R[0] = i;
    }
    for(int i = 1; i <= n; i ++)
    {
        int p;
        cin >> p;
        if(~p)
            fii[1][p].push_back(i);
        else
            R[1] = i;
    }

    for(int c = 0; c < 2; c ++)
    {
        int t = 0;
        to[c][0] = N;
        function<void(int)> dfs = [&](int u)
        {
            ti[c][u] = ++ t;
            for(int j = 1; j < 20; j ++)
                lift[c][u][j] = lift[c][lift[c][u][j - 1]][j - 1];
            for(auto x : fii[c][u])
            {
                lift[c][x][0] = u;
                dfs(x);
            }
            to[c][u] = t;
        };
        dfs(R[c]);
    }

    vector<int> p;
    function<void(int)> dfs = [&](int u)
    {
        if(ti[0][u] <= k)
            p.push_back(u);
        for(auto x : fii[0][u])
            dfs(x);
    };
    dfs(R[0]);
    for(auto x : p)
        cout << x << " ";
    cout << endl;

    auto anc = [&](int t, int a, int b)
    {
        return (ti[t][a] <= ti[t][b] && ti[t][b] <= to[t][a]);
    };

    auto Lca = [&](int t, int a, int b)
    {
        if(anc(t, a, b))
            return a;
        if(anc(t, b, a))
            return b;
        for(int j=19; ~j; j --)
            if(!anc(t, lift[t][a][j], b))
                a = lift[t][a][j];
        return lift[t][a][0];
    };

    sort(p.begin(), p.end(), [&](int a, int b)
    {
        return ti[1][a] < ti[1][b];
    });

    for(int i = 1; i < k; i ++)
        cout << "? " << p[i - 1] << " " << p[i] << endl;
    cout << "! " << endl;

    for(int i = 1; i < k; i ++)
    {
        int dc, dd, da, db;
        cin >> dc >> dd >> da >> db;
        int lca = Lca(1, p[i - 1], p[i]);
        dist[1][lca] = dist[1][p[i - 1]] - da;
        dist[1][p[i]] = dist[1][lca] + db;
        dist[0][p[i]] = dist[0][p[i - 1]] - dc + dd;
    }

    vector<array<int, 2>> Q;
    for(int i = 0; i < T; i ++)
    {
        int a, b;
        cin >> a >> b;
        Q.push_back({a, b});
    }

    for(auto [a, b] : Q)
    {
        for(int c = 0; c < 2; c ++)
        {
            int lca = Lca(c, a, b);
            cout << dist[c][a] + dist[c][b] - dist[c][lca] * 2 << " ";
        }
        cout << endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:116:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  116 |     for(auto [a, b] : Q)
      |              ^

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