oj.uz

답안 #691839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691839 2023-01-31T17:39:10 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2481 ms 290256 KB 
#include <bits/stdc++.h>

using namespace std;

void massert(bool v) {
    if (!v) {
        auto start = clock();
        int x = 1;
        while ((clock() - start) < 5 * CLOCKS_PER_SEC) {
            x <<= 1;
            x += 1;
        }
    }
}

struct Tree {
    vector<int> tin, tout, par, depth, jump;
    int logn;

    void init(vector<vector<int>> adj, int root) {
        int n = adj.size();
        int T = 0;

        tin.assign(n, -1), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);

        par[root] = jump[root] = root;

        function<void(int)> dfs = [&](int v) {
            massert(tin[v] == -1);
            tin[v] = T++;
            for (int to : adj[v]) {
                depth[to] = depth[v] + 1;
                par[to] = v;

                int p = jump[v];
                int pp = jump[p];
                if (depth[p] - depth[v] == depth[pp] - depth[p]) {
                    jump[to] = pp;
                } else {
                    jump[to] = v;
                }

                dfs(to);
            }
            tout[v] = T;
        };

        dfs(root);

        logn = __lg(n) + 1;
    }

    bool isp(int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }

    int lca(int a, int b) {
        if (isp(a, b)) {
            return a;
        }

        while (!isp(par.at(a), b)) {
            if (isp(jump[a], b)) {
                a = par[a];
            } else {
                a = jump[a];
            }
        }

        return par[a];
    }
} t1, t2;

vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
    vector<int> dist(n, -1);
    dist[root] = 0;
    vector<bool> used(n);

    function<void(int)> dfs = [&](int v) {
        massert(!used[v]);
        used[v] = true;
        for (auto [to, w] : g.at(v)) {
            if (dist.at(to) == -1) {
                dist[to] = dist[v] + w;
                dfs(to);
            }
        }
    };

    dfs(root);

    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q, t;
    cin >> n >> k >> q >> t;

    vector<int> p1(n), p2(n);

    for (int i = 0; i < n; ++i) {
        cin >> p1[i];
        p1[i] = max(int(-1), p1[i] - 1);
    }

    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
        p2[i] = max(int(-1), p2[i] - 1);
    }

    for (int i = 1; i <= k; ++i) {
        cout << i << " ";
    }
    cout << endl;

    int root1 = find(p1.begin(), p1.end(), -1) - p1.begin();
    int root2 = find(p2.begin(), p2.end(), -1) - p2.begin();

    massert(max(root1, root2) < n);

    vector<vector<int>> adj(n);

    for (int i = 0; i < n; ++i) {
        if (p1[i] != -1) {
            adj[p1[i]].push_back(i);
        }
    }

    t1.init(adj, root1);

    for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }

    for (int i = 0; i < n; ++i) {
        if (p2[i] != -1) {
            adj[p2[i]].push_back(i);
        }
    }

    t2.init(adj, root2);

    vector<pair<int, int>> questions;

    vector<int> any(n, -1);

    function<void(int)> dfs = [&](int v) {
        if (v < k) {
            any[v] = v;
        }

        for (int to : adj[v]) {
            dfs(to);

            if (any[to] != -1) {
                if (any[v] != -1) {
                    questions.emplace_back(any[v], any[to]);
                }
                any[v] = any[to];
            }
        }
    };

    dfs(root2);

    massert(questions.size() <= q);
    for (auto [x, y] : questions) {
        cout << "? " << x + 1 << " " << y + 1 << endl;
    }
    cout << "!" << endl;

    vector<vector<pair<int, int>>> g1(n), g2(n);

    int h1 = 0, h2 = 0;

    auto addEdge = [&](int t, int x, int y, int w) {
        if (x == y) {
            return;
        }
        massert(x < n && y < n && x >= 0 && y >= 0);
        (t == 0 ? g1[x] : g2[x]).emplace_back(y, w);
        (t == 0 ? g1[y] : g2[y]).emplace_back(x, -w);
    };

    for (auto [x, y] : questions) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int c1 = t1.lca(x, y);
        int c2 = t2.lca(x, y);

        if (t1.isp(c1, h1)) {
            h1 = c1;
        }
        if (t2.isp(c2, h2)) {
            h2 = c2;
        }

        addEdge(0, c1, x, a);
        addEdge(0, c1, y, b);
        addEdge(1, c2, x, c);
        addEdge(1, c2, y, d);
    }

    auto first = normalize(n, h1, g1);
    auto second = normalize(n, h2, g2);

    vector<pair<int, int>> queries(t);
    for (auto &[a, b] : queries) {
        cin >> a >> b;
        a -= 1, b -= 1;
    }

    for (auto [a, b] : queries) {
        int dist1 = first[a] - 2 * first[t1.lca(a, b)] + first[b];
        int dist2 = second[a] - 2 * second[t2.lca(a, b)] + second[b];

        cout << dist1 << " " << dist2 << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:169:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  169 |     massert(questions.size() <= q);
      |             ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1104 ms 149240 KB Output is correct
2 Correct 1105 ms 153124 KB Output is correct
3 Correct 787 ms 97380 KB Output is correct
4 Correct 764 ms 96120 KB Output is correct
5 Correct 827 ms 100292 KB Output is correct
6 Correct 1012 ms 109352 KB Output is correct
7 Correct 1092 ms 109112 KB Output is correct
8 Correct 1059 ms 108220 KB Output is correct
9 Correct 827 ms 97020 KB Output is correct
10 Correct 863 ms 99580 KB Output is correct
11 Correct 759 ms 94608 KB Output is correct
12 Correct 876 ms 98784 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1184 ms 153052 KB Output is correct
2 Correct 1095 ms 145908 KB Output is correct
3 Runtime error 740 ms 102840 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 816 ms 141360 KB Output is correct
2 Correct 843 ms 141400 KB Output is correct
3 Runtime error 550 ms 93036 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1887 ms 282188 KB Output is correct
2 Correct 1952 ms 282268 KB Output is correct
3 Runtime error 1262 ms 189452 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2291 ms 290256 KB Output is correct
2 Correct 2481 ms 289524 KB Output is correct
3 Runtime error 1534 ms 189508 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -