oj.uz

Submission #377944

# Submission time Handle Problem Language Result Execution time Memory
377944 2021-03-15T15:20:05 Z smax Werewolf (IOI18_werewolf) C++17
100 / 100
 890 ms 115416 KB 
#include "werewolf.h"

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

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

    DSU(int n) : ti(0), comp(n), 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;
        comp--;
        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 384 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 384 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 7 ms 1900 KB Output is correct
11 Correct 7 ms 1900 KB Output is correct
12 Correct 7 ms 2028 KB Output is correct
13 Correct 9 ms 2156 KB Output is correct
14 Correct 7 ms 2028 KB Output is correct
15 Correct 8 ms 2028 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 98904 KB Output is correct
2 Correct 692 ms 103128 KB Output is correct
3 Correct 697 ms 99444 KB Output is correct
4 Correct 791 ms 98276 KB Output is correct
5 Correct 809 ms 98140 KB Output is correct
6 Correct 784 ms 98500 KB Output is correct
7 Correct 720 ms 95684 KB Output is correct
8 Correct 719 ms 103128 KB Output is correct
9 Correct 650 ms 98600 KB Output is correct
10 Correct 591 ms 96368 KB Output is correct
11 Correct 597 ms 96728 KB Output is correct
12 Correct 649 ms 97368 KB Output is correct
13 Correct 724 ms 102852 KB Output is correct
14 Correct 717 ms 102744 KB Output is correct
15 Correct 715 ms 102744 KB Output is correct
16 Correct 704 ms 102892 KB Output is correct
17 Correct 653 ms 95832 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 384 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 7 ms 1900 KB Output is correct
11 Correct 7 ms 1900 KB Output is correct
12 Correct 7 ms 2028 KB Output is correct
13 Correct 9 ms 2156 KB Output is correct
14 Correct 7 ms 2028 KB Output is correct
15 Correct 8 ms 2028 KB Output is correct
16 Correct 822 ms 98904 KB Output is correct
17 Correct 692 ms 103128 KB Output is correct
18 Correct 697 ms 99444 KB Output is correct
19 Correct 791 ms 98276 KB Output is correct
20 Correct 809 ms 98140 KB Output is correct
21 Correct 784 ms 98500 KB Output is correct
22 Correct 720 ms 95684 KB Output is correct
23 Correct 719 ms 103128 KB Output is correct
24 Correct 650 ms 98600 KB Output is correct
25 Correct 591 ms 96368 KB Output is correct
26 Correct 597 ms 96728 KB Output is correct
27 Correct 649 ms 97368 KB Output is correct
28 Correct 724 ms 102852 KB Output is correct
29 Correct 717 ms 102744 KB Output is correct
30 Correct 715 ms 102744 KB Output is correct
31 Correct 704 ms 102892 KB Output is correct
32 Correct 653 ms 95832 KB Output is correct
33 Correct 890 ms 107992 KB Output is correct
34 Correct 315 ms 37788 KB Output is correct
35 Correct 820 ms 111308 KB Output is correct
36 Correct 850 ms 107352 KB Output is correct
37 Correct 887 ms 110296 KB Output is correct
38 Correct 815 ms 107864 KB Output is correct
39 Correct 773 ms 115416 KB Output is correct
40 Correct 754 ms 112724 KB Output is correct
41 Correct 706 ms 108504 KB Output is correct
42 Correct 609 ms 104280 KB Output is correct
43 Correct 806 ms 114624 KB Output is correct
44 Correct 786 ms 109520 KB Output is correct
45 Correct 664 ms 115160 KB Output is correct
46 Correct 690 ms 114876 KB Output is correct
47 Correct 702 ms 110616 KB Output is correct
48 Correct 641 ms 110168 KB Output is correct
49 Correct 681 ms 110552 KB Output is correct
50 Correct 649 ms 110260 KB Output is correct
51 Correct 691 ms 110936 KB Output is correct
52 Correct 663 ms 110808 KB Output is correct