oj.uz

답안 #691856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691856 2023-01-31T18:35:31 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2774 ms 268488 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 HLD {
    vector<int> par, siz, head, tin, tout, ord, depth;

    int dfs1(int i, vector<vector<int>> &g) {
        for (int &t: g[i]) {
            if (t != par[i]) {
                depth[t] = depth[i] + 1;
                par[t] = i;
                siz[i] += dfs1(t, g);
                if (siz[t] > siz[g[i][0]] || g[i][0] == par[i]) swap(t, g[i][0]);
            }
        }
        return siz[i];
    }

    void dfs2(int i, int &T, const vector<vector<int>> &g) {
        tin[i] = T++;
        for (int t: g[i]) {
            if (t != par[i]) {
                head[t] = (T == tin[i] + 1 ? head[i] : t);
                dfs2(t, T, g);
            }
        }
        tout[i] = T;
    }

    HLD() = default;

    HLD(vector<vector<int>> g, int r = 0)
            : par(g.size(), -1), siz(g.size(), 1), head(g.size(), r), tin(g.size()), ord(g.size()), tout(g.size()),
              depth(g.size()){
        dfs1(r, g);
        int x = 0;
        dfs2(r, x, g);
        for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
    }

    vector<pair<int, int>> path(int a, int b) {
        vector<pair<int, int>> res;
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) {
                res.emplace_back(tin[a], tin[b] + 1);
                return res;
            }
            res.emplace_back(tin[head[b]], tin[b] + 1);
        }
    }

    pair<int, int> subtree(int i) {
        return {tin[i], tin[i] + siz[i]};
    }

    int dist(int a, int b) {
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    }

    int lca(int a, int b) {
        for (;; b = par[head[b]]) {
            if (tin[b] < tin[a]) swap(a, b);
            if (tin[head[b]] <= tin[a]) return a;
        }
    }

    bool isp(int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }
} 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) {
        used[v] = true;
        for (auto [to, w] : g.at(v)) {
            if (!used[to]) {
                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 = HLD(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 = HLD(adj, root2);

    vector<pair<int, int>> questions;

    vector<int> ord(k);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return t2.tin[i] < t2.tin[j];
    });

    for (int i = 1; i < ord.size(); ++i) {
        questions.emplace_back(ord[i - 1], ord[i]);
    }

    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

Main.cpp: In constructor 'HLD::HLD(std::vector<std::vector<int> >, int)':
Main.cpp:18:44: warning: 'HLD::ord' will be initialized after [-Wreorder]
   18 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                            ^~~
Main.cpp:18:38: warning:   'std::vector<int> HLD::tout' [-Wreorder]
   18 |     vector<int> par, siz, head, tin, tout, ord, depth;
      |                                      ^~~~
Main.cpp:45:5: warning:   when initialized here [-Wreorder]
   45 |     HLD(vector<vector<int>> g, int r = 0)
      |     ^~~
Main.cpp:51:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:170:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |     for (int i = 1; i < ord.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
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: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);
      |            ~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1334 ms 129588 KB Output is correct
2 Correct 1349 ms 132716 KB Output is correct
3 Correct 1270 ms 102524 KB Output is correct
4 Correct 1171 ms 101504 KB Output is correct
5 Correct 1216 ms 105360 KB Output is correct
6 Correct 1295 ms 109812 KB Output is correct
7 Correct 1284 ms 109760 KB Output is correct
8 Correct 1240 ms 108856 KB Output is correct
9 Correct 1132 ms 102376 KB Output is correct
10 Correct 1251 ms 104700 KB Output is correct
11 Correct 1156 ms 100024 KB Output is correct
12 Correct 1191 ms 103960 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1376 ms 134368 KB Output is correct
2 Correct 1404 ms 134404 KB Output is correct
3 Runtime error 1031 ms 106748 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1160 ms 134508 KB Output is correct
2 Correct 1135 ms 134428 KB Output is correct
3 Runtime error 810 ms 98988 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2457 ms 268488 KB Output is correct
2 Correct 2468 ms 268464 KB Output is correct
3 Runtime error 1751 ms 201212 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2711 ms 268420 KB Output is correct
2 Correct 2774 ms 268428 KB Output is correct
3 Runtime error 1974 ms 201192 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -