oj.uz

Submission #277959

# Submission time Handle Problem Language Result Execution time Memory
277959 2020-08-21T08:15:04 Z hamerin Werewolf (IOI18_werewolf) C++17
100 / 100
 1844 ms 127840 KB 
#include "werewolf.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const i64 PINF = numeric_limits<int>::max();
const i64 NINF = numeric_limits<int>::min();

class disjointSet {
   public:
    vector<int> p;

    disjointSet() = default;
    explicit disjointSet(int N) {
        p.clear();
        p.resize(N);
        for (int i = 0; i < N; i++) p[i] = i;
    }

    int find(int u) { return p[u] = (p[u] == u ? u : find(p[u])); }

    void mer(int u, int v) { p[find(v)] = find(u); }

    bool sset(int u, int v) { return find(u) == find(v); }
};


namespace Helper {
    vector<int> inversePerm(const vector<int> &per) {
        int N = per.size();
        vector<int> ret(N);
        for (int i = 0; i < N; i++) ret[per[i]] = i;

        return ret;
    }

    vector<int> inversePerm(vector<int> &&per) {
        int N = per.size();
        vector<int> ret(N);
        for (int i = 0; i < N; i++) ret[per[i]] = i;

        return ret;
    }
}  // namespace Helper


class tree {
   public:
    vector<vector<int>> tr, spt;
    vector<int> in, out;
    int ord;

    tree() = default;
    explicit tree(int N) {
        tr.resize(N), spt.resize(N);
        in.resize(N), out.resize(N);
        ord = 0;
    }

    void emplace_edge(int p, int c) {
        tr[p].emplace_back(c);
    }

    void dfs_order(int h) {
        in[h] = ++ord;
        for (auto t : tr[h]) dfs_order(t);
        out[h] = ord;
    }

    void genSparseTable(int h, int p) {
        if (p >= 0) {
            int sn = 1;
            spt[h].emplace_back(p);
            while (true) {
                const auto &sppt = spt[spt[h][sn - 1]];
                if (sppt.size() < sn) break;
                spt[h].emplace_back(sppt[sn - 1]);
                ++sn;
            }
        }

        for (auto t : tr[h]) genSparseTable(t, h);
    }

    int find1(int h, int li) {
        int p = spt[h].size() - 1;
        while (true) {
            if (h == li) return h;
            if (spt[h][0] > li) return h;

            while (spt[h][p] > li) --p;
            h = spt[h][p];
            p = min(p, (int)spt[h].size() - 1);
        }
    }

    int find2(int h, int li) {
        int p = spt[h].size() - 1;
        while (true) {
            if (h == li) return h;
            if (spt[h][0] < li) return h;

            while (spt[h][p] < li) --p;
            h = spt[h][p];
            p = min(p, (int)spt[h].size() - 1);
        }
    }
};


class segTree {
   public:
    vector<int> vl;
    int N;

    segTree() = default;
    segTree(int _N) {
        vl.resize(1 << 19, NINF);
        N = _N;
    }

    void update(int s, int e, int n, int t, int ne) {
        if (s == e) {
            vl[n] = ne;
            return;
        }

        int m = (s + e) >> 1;
        int k = n << 1;
        if (t <= m)
            update(s, m, k, t, ne);
        else
            update(m + 1, e, k + 1, t, ne);

        vl[n] = max(vl[k], vl[k + 1]);
    }

    void update(int t, int ne) { update(1, N, 1, t, ne); }

    int query(int s, int e, int n, int l, int r) {
        if (r < s || e < l) return NINF;
        if (l <= s && e <= r) return vl[n];

        int m = (s + e) >> 1;
        int k = n << 1;
        return max(query(s, m, k, l, r), query(m + 1, e, k + 1, l, r));
    }

    int query(int l, int r) { return query(1, N, 1, l, r); }
};


using qi = tuple<int, int, int, int>;
using pei = tuple<int, int, int, int, int>;

vector<int> check_validity(int N,
                           vector<int> X, vector<int> Y,
                           vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int Q = (int)S.size();
    int M = (int)X.size();

    vector<vector<int>> graph(N);
    for (int i = 0; i < M; i++) {
        graph[X[i]].emplace_back(Y[i]);
        graph[Y[i]].emplace_back(X[i]);
    }


    tree tree1(N);
    disjointSet dS1(N);
    for (int i = 1; i < N; i++) {
        set<int> toemplace;
        for (auto j : graph[i]) {
            if (j < i) toemplace.emplace(dS1.find(j));
        }

        for (auto j : toemplace) {
            dS1.mer(i, j);
            tree1.emplace_edge(i, j);
        }
    }

    tree1.dfs_order(N - 1);
    tree1.genSparseTable(N - 1, -1);

    tree tree2(N);
    disjointSet dS2(N);
    for (int i = N - 2; i >= 0; i--) {
        set<int> toemplace;
        for (auto j : graph[i]) {
            if (j > i) toemplace.emplace(dS2.find(j));
        }

        for (auto j : toemplace) {
            dS2.mer(i, j);
            tree2.emplace_edge(i, j);
        }
    }

    tree2.dfs_order(0);
    tree2.genSparseTable(0, -1);


    vector<pi> points;
    for (int i = 0; i < N; i++) {
        points.emplace_back(tree1.in[i], tree2.in[i]);
    }
    sort(iterall(points));

    vector<qi> queries(Q);
    for (int i = 0; i < Q; i++) {
        queries[i] = {S[i], E[i], L[i], R[i]};
    }

    vector<pei> rectq;  // lx, hx, ly, hy, idx
    for (int i = 0; i < Q; i++) {
        auto [s, e, l, r] = queries[i];
        auto n1 = tree1.find1(e, r);
        auto n2 = tree2.find2(s, l);
        rectq.emplace_back(tree1.in[n1], tree1.out[n1],
                           tree2.in[n2], tree2.out[n2], i);
    }
    sort(iterall(rectq), [](const pei &l, const pei &r) {
        return get<1>(l) < get<1>(r);
    });


    vector<int> ret(Q);
    int ptr = 0;
    auto sT = segTree(N);
    for (auto [lx, hx, ly, hy, idx] : rectq) {
        while (ptr < N && points[ptr].first <= hx) {
            auto [x, y] = points[ptr];
            sT.update(y, x);
            ++ptr;
        }

        if (sT.query(ly, hy) >= lx) ret[idx] = 1;
    }

    return ret;
}

Compilation message

werewolf.cpp: In member function 'void tree::genSparseTable(int, int)':
werewolf.cpp:90:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |                 if (sppt.size() < sn) break;
      |                     ~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 3 ms 2432 KB Output is correct
9 Correct 3 ms 2464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 3 ms 2432 KB Output is correct
9 Correct 3 ms 2464 KB Output is correct
10 Correct 15 ms 3968 KB Output is correct
11 Correct 20 ms 3960 KB Output is correct
12 Correct 10 ms 3712 KB Output is correct
13 Correct 17 ms 4224 KB Output is correct
14 Correct 12 ms 4096 KB Output is correct
15 Correct 17 ms 4088 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 82272 KB Output is correct
2 Correct 1451 ms 104932 KB Output is correct
3 Correct 1160 ms 97504 KB Output is correct
4 Correct 1080 ms 89544 KB Output is correct
5 Correct 1052 ms 89060 KB Output is correct
6 Correct 1144 ms 87152 KB Output is correct
7 Correct 1056 ms 82532 KB Output is correct
8 Correct 1409 ms 105228 KB Output is correct
9 Correct 992 ms 97476 KB Output is correct
10 Correct 856 ms 89440 KB Output is correct
11 Correct 798 ms 89056 KB Output is correct
12 Correct 872 ms 87268 KB Output is correct
13 Correct 1484 ms 119400 KB Output is correct
14 Correct 1605 ms 119500 KB Output is correct
15 Correct 1569 ms 119528 KB Output is correct
16 Correct 1558 ms 119524 KB Output is correct
17 Correct 1028 ms 82584 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 3 ms 2432 KB Output is correct
9 Correct 3 ms 2464 KB Output is correct
10 Correct 15 ms 3968 KB Output is correct
11 Correct 20 ms 3960 KB Output is correct
12 Correct 10 ms 3712 KB Output is correct
13 Correct 17 ms 4224 KB Output is correct
14 Correct 12 ms 4096 KB Output is correct
15 Correct 17 ms 4088 KB Output is correct
16 Correct 1055 ms 82272 KB Output is correct
17 Correct 1451 ms 104932 KB Output is correct
18 Correct 1160 ms 97504 KB Output is correct
19 Correct 1080 ms 89544 KB Output is correct
20 Correct 1052 ms 89060 KB Output is correct
21 Correct 1144 ms 87152 KB Output is correct
22 Correct 1056 ms 82532 KB Output is correct
23 Correct 1409 ms 105228 KB Output is correct
24 Correct 992 ms 97476 KB Output is correct
25 Correct 856 ms 89440 KB Output is correct
26 Correct 798 ms 89056 KB Output is correct
27 Correct 872 ms 87268 KB Output is correct
28 Correct 1484 ms 119400 KB Output is correct
29 Correct 1605 ms 119500 KB Output is correct
30 Correct 1569 ms 119528 KB Output is correct
31 Correct 1558 ms 119524 KB Output is correct
32 Correct 1028 ms 82584 KB Output is correct
33 Correct 1280 ms 97252 KB Output is correct
34 Correct 456 ms 29924 KB Output is correct
35 Correct 1583 ms 102400 KB Output is correct
36 Correct 1353 ms 97224 KB Output is correct
37 Correct 1475 ms 101088 KB Output is correct
38 Correct 1260 ms 98276 KB Output is correct
39 Correct 1335 ms 126764 KB Output is correct
40 Correct 1622 ms 106424 KB Output is correct
41 Correct 1162 ms 100112 KB Output is correct
42 Correct 1018 ms 97172 KB Output is correct
43 Correct 1660 ms 121600 KB Output is correct
44 Correct 1203 ms 100960 KB Output is correct
45 Correct 1195 ms 127840 KB Output is correct
46 Correct 1175 ms 126660 KB Output is correct
47 Correct 1844 ms 119648 KB Output is correct
48 Correct 1594 ms 119300 KB Output is correct
49 Correct 1424 ms 119388 KB Output is correct
50 Correct 1480 ms 119360 KB Output is correct
51 Correct 1643 ms 106072 KB Output is correct
52 Correct 1413 ms 106132 KB Output is correct