oj.uz

Submission #926846

# Submission time Handle Problem Language Result Execution time Memory
926846 2024-02-13T23:30:11 Z bobbilyking Werewolf (IOI18_werewolf) C++17
100 / 100
 2064 ms 135608 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
 
using ll = int;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define A(a) (a).begin(), (a).end()
using pl = pair<ll, ll>;
 
using vl = vector<ll>;
#define K first 
#define V second
#define NN 200010
ll parent[NN];
vl dsuSet[NN];
ll find(ll i) {
    while ( i - parent[i]) i = parent[i];
    return i;
}
 
optional<pair<pl, vl>> merge(ll i, ll j) {
    i = find(i), j = find(j);
    if (i-j) {
        if (dsuSet[i].size() < dsuSet[j].size()) swap(i, j);
        parent[j] = i;
        dsuSet[i].insert(dsuSet[i].end(), A(dsuSet[j]));
        return {pair(pair(i, j), dsuSet[j])};
    }
    return {};
}
 
// another alternate form of the kruskal reconstruction tree
// We're trying to maintain, "does node E exists in my KRT subtree?"
// Hard to maintain with normal KRT.
// Instead, let's store in the event-KRT 
 
namespace krt {
    ll parent[NN];
    map<ll, ll> nodesInSubtree[NN]; 
 
    ll pw[NN];
    
    ll find(ll i) {
        while (i - parent[i]) i = parent[i];
        return i;
    }
 
    void merge(ll i, ll j, ll w) {
        i = find(i), j = find(j);
        if (i-j) {
            if (nodesInSubtree[i].size() < nodesInSubtree[j].size()) {
                swap(i, j);
            }
            for (auto &[x, _]: nodesInSubtree[j]) nodesInSubtree[i][x] = w;
 
            pw[j] = w;
            parent[j] = i;
        }
    }
 
    void init(ll n) {
        F(i, 0, n) {
            nodesInSubtree[i][i] = n-1; 
            parent[i] = i;
        }
    }
 
    void change(ll node, ll relabelFrom, ll relabelTo) {
        // cout << "CHANGE " << endl;
        // cout << "START NODE: " << node << " " << relabelFrom << " -> " << relabelTo << endl;
        // for (auto [k, v]: nodesInSubtree[node]) cout << k << " " << v << " | "; cout << endl;

        // This case happens when we relabel to the root for multiple nodes. In this case, we've already compressed the relabeling, so we're good.
        // (Here is an example of a data structure where it's trivial to update things from bototm up, but hard to know what to dfs into top-down).
        if (!nodesInSubtree[node].count(relabelFrom)) return; 


        // this is correct since we're just locally compressing the sequence, we're not doing anything fancy like passing up the time. 
        // in the brute force version, we'd maintain the entire sequence of relabeled nodes per thing.
        // but obviously, we can compress all of those, and then only the maximum time (e.g. earliest suffix) matters.
        ll v = nodesInSubtree[node][relabelFrom];
        nodesInSubtree[node].erase(relabelFrom);
        
        nodesInSubtree[node][relabelTo] = max(nodesInSubtree[node][relabelTo], v);
 
        if (node != parent[node]) change(parent[node], relabelFrom, relabelTo);
    }
 
    // this is a bit... sus.
    bool query(ll node, ll searchLabel, ll w) {
        if (node != parent[node] and pw[node] >= w) return query(parent[node], searchLabel, w);

        // cout << "WTF? " << searchLabel << " " << w << endl;
        // for (auto [k, v]: nodesInSubtree[node]) cout << k << " " << v << endl;

        auto it = nodesInSubtree[node].find(searchLabel); 
        if (it != nodesInSubtree[node].end() and it->V >= w)  return true;
        return false;
    }
}
 
 
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
 
    ll Q = R.size();
    vector<vector<pl>> queries(N);
    std::vector<int> ans(Q);
 
    F(i, 0, Q) {
        queries[R[i]].emplace_back(L[i], i);
    }
 
    vector<vector<pl>> edges(N), edgesPre(N);
    F(i, 0, X.size()) {
        edges[max(X[i], Y[i])].emplace_back(X[i], Y[i]);
        edgesPre[min(X[i], Y[i])].emplace_back(X[i], Y[i]);
    }
 
    // E means u can go from [L, N-1] in the suffix dSU
    krt::init(N);
    for (ll i = N-1; i >= 0; --i) for (auto [x, y]: edgesPre[i]) {
        krt::merge(x, y, i);
    }
 
    // S means u can go from [0, R] in the prefix DSU
 
    F(i, 0, N) {
        parent[i] = i;
        dsuSet[i] = {i};
    }
 
    F(right, 0, N) {
        for (auto &[x, y]: edges[right]) {
            auto result = merge(x, y);
            if (result.has_value()) {
                auto [relabel, nodes] = *result;
                for (auto x: nodes) {
                    krt::change(x, relabel.V, relabel.K);
                }
            }
        }

        for (auto &[left, qidx]: queries[right]) {
            // cout << "Current prefix dsu: " << endl;
            // F(i, 0, N) cout << find(i) << " "; cout << endl;
            // cout << "??? " << E[qidx] << " " << S[qidx] << " " << find(S[qidx]) << endl;

            ans[qidx] = krt::query(S[qidx], find(E[qidx]), left);
        }
    }
 
    return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:6:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define F(i, l, r) for (ll i = (l); i < (r); ++i)
      |                                       ^
werewolf.cpp:116:5: note: in expansion of macro 'F'
  116 |     F(i, 0, X.size()) {
      |     ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 3 ms 15704 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 4 ms 15968 KB Output is correct
8 Correct 4 ms 15960 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 3 ms 15704 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 4 ms 15968 KB Output is correct
8 Correct 4 ms 15960 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 9 ms 16988 KB Output is correct
11 Correct 10 ms 17052 KB Output is correct
12 Correct 11 ms 17244 KB Output is correct
13 Correct 8 ms 16988 KB Output is correct
14 Correct 10 ms 17240 KB Output is correct
15 Correct 9 ms 17244 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 126444 KB Output is correct
2 Correct 421 ms 99416 KB Output is correct
3 Correct 547 ms 110680 KB Output is correct
4 Correct 835 ms 126416 KB Output is correct
5 Correct 931 ms 128512 KB Output is correct
6 Correct 1412 ms 133420 KB Output is correct
7 Correct 2064 ms 135608 KB Output is correct
8 Correct 420 ms 99600 KB Output is correct
9 Correct 581 ms 111640 KB Output is correct
10 Correct 792 ms 124620 KB Output is correct
11 Correct 844 ms 125840 KB Output is correct
12 Correct 1315 ms 133888 KB Output is correct
13 Correct 383 ms 95572 KB Output is correct
14 Correct 378 ms 95312 KB Output is correct
15 Correct 383 ms 95500 KB Output is correct
16 Correct 373 ms 95316 KB Output is correct
17 Correct 1956 ms 133676 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15964 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 3 ms 15704 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 16216 KB Output is correct
7 Correct 4 ms 15968 KB Output is correct
8 Correct 4 ms 15960 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 9 ms 16988 KB Output is correct
11 Correct 10 ms 17052 KB Output is correct
12 Correct 11 ms 17244 KB Output is correct
13 Correct 8 ms 16988 KB Output is correct
14 Correct 10 ms 17240 KB Output is correct
15 Correct 9 ms 17244 KB Output is correct
16 Correct 2041 ms 126444 KB Output is correct
17 Correct 421 ms 99416 KB Output is correct
18 Correct 547 ms 110680 KB Output is correct
19 Correct 835 ms 126416 KB Output is correct
20 Correct 931 ms 128512 KB Output is correct
21 Correct 1412 ms 133420 KB Output is correct
22 Correct 2064 ms 135608 KB Output is correct
23 Correct 420 ms 99600 KB Output is correct
24 Correct 581 ms 111640 KB Output is correct
25 Correct 792 ms 124620 KB Output is correct
26 Correct 844 ms 125840 KB Output is correct
27 Correct 1315 ms 133888 KB Output is correct
28 Correct 383 ms 95572 KB Output is correct
29 Correct 378 ms 95312 KB Output is correct
30 Correct 383 ms 95500 KB Output is correct
31 Correct 373 ms 95316 KB Output is correct
32 Correct 1956 ms 133676 KB Output is correct
33 Correct 1098 ms 106004 KB Output is correct
34 Correct 154 ms 53172 KB Output is correct
35 Correct 785 ms 97060 KB Output is correct
36 Correct 1169 ms 107172 KB Output is correct
37 Correct 818 ms 97612 KB Output is correct
38 Correct 1085 ms 104700 KB Output is correct
39 Correct 745 ms 113236 KB Output is correct
40 Correct 690 ms 108108 KB Output is correct
41 Correct 831 ms 98764 KB Output is correct
42 Correct 1236 ms 108844 KB Output is correct
43 Correct 723 ms 100260 KB Output is correct
44 Correct 819 ms 98184 KB Output is correct
45 Correct 645 ms 106204 KB Output is correct
46 Correct 762 ms 115024 KB Output is correct
47 Correct 379 ms 95508 KB Output is correct
48 Correct 388 ms 95568 KB Output is correct
49 Correct 378 ms 95568 KB Output is correct
50 Correct 390 ms 95776 KB Output is correct
51 Correct 712 ms 107924 KB Output is correct
52 Correct 705 ms 108352 KB Output is correct