oj.uz

답안 #691857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
691857 2023-01-31T18:37:01 Z piOOE Prize (CEOI22_prize) C++17
10 / 100
 2853 ms 268620 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 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();

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1344 ms 129596 KB Output is correct
2 Correct 1299 ms 132592 KB Output is correct
3 Correct 1101 ms 102524 KB Output is correct
4 Correct 1177 ms 101408 KB Output is correct
5 Correct 1223 ms 105360 KB Output is correct
6 Correct 1237 ms 109720 KB Output is correct
7 Correct 1210 ms 109632 KB Output is correct
8 Correct 1206 ms 108988 KB Output is correct
9 Correct 1089 ms 102544 KB Output is correct
10 Correct 1146 ms 104620 KB Output is correct
11 Correct 1073 ms 100044 KB Output is correct
12 Correct 1118 ms 103956 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1310 ms 134440 KB Output is correct
2 Correct 1261 ms 134536 KB Output is correct
3 Runtime error 982 ms 106588 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1089 ms 134528 KB Output is correct
2 Correct 1111 ms 134424 KB Output is correct
3 Runtime error 808 ms 98876 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2438 ms 268464 KB Output is correct
2 Correct 2437 ms 268576 KB Output is correct
3 Runtime error 1694 ms 201420 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2853 ms 268620 KB Output is correct
2 Correct 2573 ms 268468 KB Output is correct
3 Runtime error 2029 ms 201264 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -