oj.uz

Submission #1094871

# Submission time Handle Problem Language Result Execution time Memory
1094871 2024-09-30T17:32:36 Z MateiKing80 Prize (CEOI22_prize) C++14
100 / 100
 2397 ms 551296 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 301284 KB Output is correct
2 Correct 1064 ms 301624 KB Output is correct
3 Correct 801 ms 249612 KB Output is correct
4 Correct 759 ms 249592 KB Output is correct
5 Correct 803 ms 249716 KB Output is correct
6 Correct 1119 ms 259644 KB Output is correct
7 Correct 1167 ms 259608 KB Output is correct
8 Correct 1112 ms 259620 KB Output is correct
9 Correct 795 ms 249756 KB Output is correct
10 Correct 729 ms 249708 KB Output is correct
11 Correct 755 ms 249616 KB Output is correct
12 Correct 822 ms 249812 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1074 ms 301772 KB Output is correct
2 Correct 1024 ms 301188 KB Output is correct
3 Correct 793 ms 249696 KB Output is correct
4 Correct 823 ms 249896 KB Output is correct
5 Correct 864 ms 249676 KB Output is correct
6 Correct 1219 ms 259540 KB Output is correct
7 Correct 1237 ms 259660 KB Output is correct
8 Correct 1264 ms 259676 KB Output is correct
9 Correct 1078 ms 258308 KB Output is correct
10 Correct 1128 ms 258384 KB Output is correct
11 Correct 1022 ms 258196 KB Output is correct
12 Correct 1008 ms 258580 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 293516 KB Output is correct
2 Correct 924 ms 293504 KB Output is correct
3 Correct 597 ms 242112 KB Output is correct
4 Correct 590 ms 242112 KB Output is correct
5 Correct 627 ms 242068 KB Output is correct
6 Correct 808 ms 252140 KB Output is correct
7 Correct 799 ms 252104 KB Output is correct
8 Correct 790 ms 252280 KB Output is correct
9 Correct 683 ms 250812 KB Output is correct
10 Correct 708 ms 250720 KB Output is correct
11 Correct 720 ms 250636 KB Output is correct
12 Correct 727 ms 250812 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2154 ms 542220 KB Output is correct
2 Correct 2025 ms 541232 KB Output is correct
3 Correct 1464 ms 438848 KB Output is correct
4 Correct 1429 ms 438940 KB Output is correct
5 Correct 1510 ms 438760 KB Output is correct
6 Correct 2054 ms 459240 KB Output is correct
7 Correct 2007 ms 459172 KB Output is correct
8 Correct 2025 ms 458908 KB Output is correct
9 Correct 1745 ms 456336 KB Output is correct
10 Correct 1714 ms 456508 KB Output is correct
11 Correct 1703 ms 456092 KB Output is correct
12 Correct 1733 ms 456596 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2256 ms 551296 KB Output is correct
2 Correct 2258 ms 551116 KB Output is correct
3 Correct 1677 ms 447592 KB Output is correct
4 Correct 1605 ms 447800 KB Output is correct
5 Correct 1641 ms 447500 KB Output is correct
6 Correct 2397 ms 467604 KB Output is correct
7 Correct 2339 ms 467444 KB Output is correct
8 Correct 2360 ms 467552 KB Output is correct
9 Correct 2171 ms 464692 KB Output is correct
10 Correct 1995 ms 464496 KB Output is correct
11 Correct 2099 ms 464672 KB Output is correct
12 Correct 2093 ms 464980 KB Output is correct