oj.uz

Submission #377946

# Submission time Handle Problem Language Result Execution time Memory
377946 2021-03-15T15:21:01 Z smax Werewolf (IOI18_werewolf) C++17
100 / 100
 936 ms 107736 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int ti;
    vector<int> par, in, out, order;
    vector<vector<int>> adj;

    DSU(int n) : ti(0), par(n), in(n), out(n), order({n}), adj(n) {
        iota(par.begin(), par.end(), 0);
    }

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

    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v)
            return;
        par.push_back((int) par.size());
        par[u] = par[v] = (int) par.size() - 1;
        in.emplace_back();
        out.emplace_back();
        adj.push_back({u, v});
    }

    void dfs(int u) {
        in[u] = ++ti;
        order.push_back(u);
        for (int v : adj[u])
            dfs(v);
        out[u] = ti;
    }
};

template<typename T>
struct BIT {
    int n;
    vector<T> bit;

    BIT(int _n) : n(_n), bit(n + 1) {}

    T query(int i) {
        T ret = 0;
        for (; i>0; i-=i&-i)
            ret += bit[i];
        return ret;
    }

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

    void update(int i, T val) {
        for (; i<=n; i+=i&-i)
            bit[i] += val;
    }
};

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) {
    int m = (int) X.size(), q = (int) S.size();
    vector<vector<int>> adj(N);
    for (int i=0; i<m; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    vector<vector<int>> queryL(N), queryR(N);
    for (int i=0; i<q; i++) {
        queryL[L[i]].push_back(i);
        queryR[R[i]].push_back(i);
    }

    DSU inc(N), dec(N);
    for (int u=0; u<N; u++) {
        for (int v : adj[u])
            if (v < u)
                inc.unite(u, v);
        for (int i : queryR[u])
            E[i] = inc.find(E[i]);
    }
    for (int u=N-1; u>=0; u--) {
        for (int v : adj[u])
            if (v > u)
                dec.unite(u, v);
        for (int i : queryL[u])
            S[i] = dec.find(S[i]);
    }
    inc.dfs(inc.find(0));
    dec.dfs(dec.find(0));

    int o1 = (int) inc.order.size(), o2 = (int) dec.order.size();
    vector<vector<pair<int, int>>> pts(o1);
    BIT<int> bit(o2);
    vector<int> ret(q);
    for (int i=0; i<q; i++) {
        pts[inc.in[E[i]] - 1].emplace_back(i, -1);
        pts[inc.out[E[i]]].emplace_back(i, 1);
    }
    for (int i=0; i<o1; i++) {
        if (inc.order[i] < N)
            bit.update(dec.in[inc.order[i]], 1);
        for (auto [j, c] : pts[i])
            ret[j] += bit.query(dec.in[S[j]], dec.out[S[j]]) * c;
    }

    for (int i=0; i<q; i++)
        ret[i] = ret[i] > 0;
    return ret;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 9 ms 1900 KB Output is correct
11 Correct 9 ms 1900 KB Output is correct
12 Correct 8 ms 1960 KB Output is correct
13 Correct 7 ms 2028 KB Output is correct
14 Correct 6 ms 2028 KB Output is correct
15 Correct 7 ms 2028 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 98648 KB Output is correct
2 Correct 684 ms 102616 KB Output is correct
3 Correct 672 ms 99416 KB Output is correct
4 Correct 704 ms 97752 KB Output is correct
5 Correct 685 ms 97624 KB Output is correct
6 Correct 799 ms 98048 KB Output is correct
7 Correct 650 ms 95064 KB Output is correct
8 Correct 702 ms 102524 KB Output is correct
9 Correct 672 ms 98124 KB Output is correct
10 Correct 572 ms 95804 KB Output is correct
11 Correct 575 ms 96088 KB Output is correct
12 Correct 654 ms 96828 KB Output is correct
13 Correct 746 ms 102232 KB Output is correct
14 Correct 753 ms 102232 KB Output is correct
15 Correct 711 ms 102232 KB Output is correct
16 Correct 705 ms 102232 KB Output is correct
17 Correct 680 ms 95192 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 9 ms 1900 KB Output is correct
11 Correct 9 ms 1900 KB Output is correct
12 Correct 8 ms 1960 KB Output is correct
13 Correct 7 ms 2028 KB Output is correct
14 Correct 6 ms 2028 KB Output is correct
15 Correct 7 ms 2028 KB Output is correct
16 Correct 847 ms 98648 KB Output is correct
17 Correct 684 ms 102616 KB Output is correct
18 Correct 672 ms 99416 KB Output is correct
19 Correct 704 ms 97752 KB Output is correct
20 Correct 685 ms 97624 KB Output is correct
21 Correct 799 ms 98048 KB Output is correct
22 Correct 650 ms 95064 KB Output is correct
23 Correct 702 ms 102524 KB Output is correct
24 Correct 672 ms 98124 KB Output is correct
25 Correct 572 ms 95804 KB Output is correct
26 Correct 575 ms 96088 KB Output is correct
27 Correct 654 ms 96828 KB Output is correct
28 Correct 746 ms 102232 KB Output is correct
29 Correct 753 ms 102232 KB Output is correct
30 Correct 711 ms 102232 KB Output is correct
31 Correct 705 ms 102232 KB Output is correct
32 Correct 680 ms 95192 KB Output is correct
33 Correct 911 ms 99928 KB Output is correct
34 Correct 309 ms 26780 KB Output is correct
35 Correct 874 ms 103000 KB Output is correct
36 Correct 868 ms 99160 KB Output is correct
37 Correct 936 ms 102276 KB Output is correct
38 Correct 886 ms 99672 KB Output is correct
39 Correct 782 ms 107736 KB Output is correct
40 Correct 783 ms 101588 KB Output is correct
41 Correct 731 ms 100204 KB Output is correct
42 Correct 656 ms 96220 KB Output is correct
43 Correct 895 ms 104884 KB Output is correct
44 Correct 882 ms 101336 KB Output is correct
45 Correct 726 ms 106840 KB Output is correct
46 Correct 730 ms 106828 KB Output is correct
47 Correct 735 ms 102360 KB Output is correct
48 Correct 729 ms 102360 KB Output is correct
49 Correct 737 ms 102360 KB Output is correct
50 Correct 707 ms 102216 KB Output is correct
51 Correct 714 ms 99800 KB Output is correct
52 Correct 761 ms 99544 KB Output is correct