답안 #691853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691853 2023-01-31T18:25:29 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
3007 ms 290224 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) {
            cout << "fuck" << endl;
            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)) {
            massert(to >= 0 && to < n);
            if (dist.at(to) == -1) {
                dist[to] = dist[v] + w;
                dfs(to);
            }
        }
    };

    dfs(root);

    return dist;
}

int main() {
    int n, k, q, t;
    cin >> n >> k >> q >> t;

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

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

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

    for (int i = 1; i <= k; ++i) {
        cout << i << " \n"[i == k];
    }
    cout.flush();

    assert(max(root1, root2) < n && min(root1, root2) >= 0);

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

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:174:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |     assert(questions.size() <= q);
      |            ~~~~~~~~~~~~~~~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1335 ms 149080 KB Output is correct
2 Correct 1483 ms 153140 KB Output is correct
3 Correct 1014 ms 97452 KB Output is correct
4 Correct 1014 ms 95964 KB Output is correct
5 Correct 1144 ms 100248 KB Output is correct
6 Correct 1317 ms 109028 KB Output is correct
7 Correct 1372 ms 109048 KB Output is correct
8 Correct 1305 ms 108148 KB Output is correct
9 Correct 1034 ms 97012 KB Output is correct
10 Correct 1276 ms 99464 KB Output is correct
11 Correct 968 ms 94612 KB Output is correct
12 Correct 1052 ms 98792 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1414 ms 153156 KB Output is correct
2 Correct 1484 ms 145756 KB Output is correct
3 Runtime error 980 ms 102708 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1018 ms 141380 KB Output is correct
2 Correct 1010 ms 141196 KB Output is correct
3 Runtime error 821 ms 92984 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2390 ms 282240 KB Output is correct
2 Correct 2342 ms 282276 KB Output is correct
3 Runtime error 1615 ms 189472 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2687 ms 290224 KB Output is correct
2 Correct 3007 ms 289508 KB Output is correct
3 Runtime error 1762 ms 189404 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -