oj.uz

답안 #691796

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

using namespace std;

#define int int64_t

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.resize(n), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);

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

        function<void(int)> dfs = [&](int v) {
            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[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;

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

    dfs(root);

    return dist;
}

int32_t 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();

    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;
        }

        vector<int> alive;

        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);

    if (questions.size() > q) {
        while (true) {
            cout << "axaxax" << endl;
        }
    }
    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) {
        (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] + first[b] - 2 * first[t1.lca(a, b)];
        int dist2 = second[a] + second[b] - 2 * second[t2.lca(a, b)];

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

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1229 ms 194844 KB Output is correct
2 Correct 1297 ms 202884 KB Output is correct
3 Correct 867 ms 136428 KB Output is correct
4 Correct 847 ms 134228 KB Output is correct
5 Correct 1004 ms 141900 KB Output is correct
6 Correct 1308 ms 151012 KB Output is correct
7 Correct 1345 ms 150888 KB Output is correct
8 Correct 1210 ms 149108 KB Output is correct
9 Correct 910 ms 135924 KB Output is correct
10 Correct 921 ms 140384 KB Output is correct
11 Correct 895 ms 131712 KB Output is correct
12 Correct 910 ms 139088 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1376 ms 201844 KB Output is correct
2 Correct 1283 ms 191640 KB Output is correct
3 Runtime error 751 ms 142256 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 887 ms 184348 KB Output is correct
2 Correct 873 ms 184340 KB Output is correct
3 Runtime error 584 ms 129284 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2049 ms 368308 KB Output is correct
2 Correct 2071 ms 368308 KB Output is correct
3 Runtime error 1243 ms 258052 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2416 ms 380096 KB Output is correct
2 Correct 2652 ms 377272 KB Output is correct
3 Runtime error 1407 ms 265896 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -