oj.uz

답안 #691763

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

using namespace std;

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

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

        function<void(int)> dfs = [&](int v) {
            tin[v] = T++;
            for (int to : adj[v]) {
                par[to] = v;
                dfs(to);
            }
            tout[v] = T;
        };

        dfs(root);

        par[root] = root;

        logn = __lg(n) + 1;

        jump = vector(logn, vector<int>(n));
        jump[0] = par;

        for (int j = 1; j < logn; ++j) {
            for (int i = 0; i < n; ++i) {
                jump[j][i] = jump[j - 1][jump[j - 1][i]];
            }
        }
    }

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

        for (int i = logn - 1; i >= 0; --i) {
            if (!isp(jump[i][a], b)) {
                a = jump[i][a];
            }
        }

        return jump[0][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;
                assert(dist[to] != -1);
                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(-1, p1[i] - 1);
    }

    for (int i = 0; i < n; ++i) {
        cin >> p2[i];
        p2[i] = max(-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) {
                alive.push_back(to);
            }
        }

        if (alive.empty()) {
            return;
        }

        any[v] = any[alive[0]];

        if (alive.size() == 1) {
            if (v < k) {
                questions.emplace_back(any[alive[0]], v);
            }
        } else {
            for (int i = 1; i < alive.size(); ++i) {
                questions.emplace_back(any[alive[0]], any[alive[i]]);
            }
        }
    };

    dfs(root2);

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

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

    int h1 = -1, h2 = -1;

    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 (h1 == -1 || t1.isp(c1, h1)) {
            h1 = c1;
        }
        if (h2 == -1 || 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 lambda function:
Main.cpp:157:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |             for (int i = 1; i < alive.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1347 ms 217652 KB Output is correct
2 Correct 1407 ms 221544 KB Output is correct
3 Correct 1176 ms 163592 KB Output is correct
4 Correct 1111 ms 162860 KB Output is correct
5 Correct 1283 ms 167068 KB Output is correct
6 Correct 1654 ms 175920 KB Output is correct
7 Correct 1672 ms 175880 KB Output is correct
8 Correct 1588 ms 174844 KB Output is correct
9 Correct 1123 ms 163232 KB Output is correct
10 Correct 1111 ms 166200 KB Output is correct
11 Correct 950 ms 161216 KB Output is correct
12 Correct 1090 ms 165492 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1547 ms 220628 KB Output is correct
2 Correct 1400 ms 214252 KB Output is correct
3 Runtime error 786 ms 167316 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 913 ms 208052 KB Output is correct
2 Correct 907 ms 207908 KB Output is correct
3 Runtime error 558 ms 159496 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2267 ms 423116 KB Output is correct
2 Correct 2281 ms 423188 KB Output is correct
3 Runtime error 1209 ms 330524 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2614 ms 434688 KB Output is correct
2 Correct 2551 ms 434604 KB Output is correct
3 Runtime error 1501 ms 330532 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -