oj.uz

Submission #241977

# Submission time Handle Problem Language Result Execution time Memory
241977 2020-06-26T13:06:36 Z abacaba Werewolf (IOI18_werewolf) C++14
100 / 100
 1250 ms 152680 KB 
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int inf = 2e9;
const int mod = 998244353;
const int N = 2e5 + 15;
const int L = 19;
const int M = 4e5 + 15;
int n, q;
vector <int> g[N];

int l[M], r[M];

int k[M], tin[M], tout[M], tt, up[L][M];

int backtin[N];

struct dsu {
    int p[N], sz[N];
    dsu() {
        for(int i = 0; i < N; ++i)
            p[i] = i, sz[i] = 1;
    }
    int find(int v) {
        if(v == p[v])
            return v;
        return p[v] = find(p[v]);
    }
    void unio(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            if(sz[a] < sz[b])
                swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
        }
    }
} rt;

set <int> is[N];

struct dsu_with_set {
    int p[N];
    dsu_with_set() {
        for(int i = 0; i < N; ++i)
            p[i] = i;
    }
    int find(int v) {
        if(v == p[v])
            return v;
        return p[v] = find(p[v]);
    }
    void unio(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            if(is[a].size() < is[b].size())
                swap(a, b);
            p[b] = a;
            is[a].insert(is[b].begin(), is[b].end());
        }
    }
} s;

struct query {
    int l, r, s, e, ind;
    bool operator < (const query &rhs) const {
        return r < rhs.r;
    }
} qs[N];

vector <pii> e;

int cur[N];

inline int getk(int v, int val) {
    for(int i = L - 1; i >= 0; --i)
        if(k[up[i][v]] >= val)
            v = up[i][v];
    return v;
}

void build(int v, int p) {
    up[0][v] = p;
    for(int i = 1; i < L; ++i)
        up[i][v] = up[i-1][up[i-1][v]];
    if(v < n) {
        tin[v] = tout[v] = tt++;
    }
    else {
        build(l[v], v);
        build(r[v], v);
        tin[v] = tin[l[v]];
        tout[v] = tout[r[v]];
    }
}

inline void build_reachability_tree() {
    sort(e.begin(), e.end(), [&](pii a, pii b) {
        return min(a.f, a.se) > min(b.f, b.se);
    });
    int nw = n;
    for(int i = 0; i < n; ++i)
        cur[i] = k[i] = i;
    for(int i = 0; i < e.size(); ++i) {
        int u = e[i].f, v = e[i].se;
        if(rt.find(u) != rt.find(v)) {
            l[nw] = cur[rt.find(u)];
            r[nw] = cur[rt.find(v)];
            rt.unio(u, v);
            k[nw] = min(u, v);
            cur[rt.find(u)] = nw++;
        }
    }
    build(nw - 1, nw - 1);
    for(int i = 0; i < n; ++i)
        backtin[tin[i]] = i;
    for(int i = 0; i < n; ++i)
        is[i].insert(tin[i]);
}

inline void add(int v) {
    for(int to : g[v])
        if(to < v)
            s.unio(to, v);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = N, q = S.size();
    vector<int> ans(q, 0);
    for(int i = 0; i < X.size(); ++i) {
        g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
        e.pb({X[i], Y[i]});
    }
    build_reachability_tree();
    for(int i = 0; i < q; ++i)
        qs[i] = {L[i], R[i], S[i], E[i], i};
    sort(qs, qs + q);
    for(int i = 0, ptr = 0; i < q; ++i) {
        while(ptr < n && ptr <= qs[i].r)
            add(ptr++);
        int p = getk(qs[i].s, qs[i].l);
        set <int>::iterator it = is[s.find(qs[i].e)].lower_bound(tin[p]);
        ans[qs[i].ind] = (it != is[s.find(qs[i].e)].end() && *it <= tout[p]);
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void build_reachability_tree()':
werewolf.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < e.size(); ++i) {
                    ~~^~~~~~~~~~
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:191:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); ++i) {
                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17024 KB Output is correct
2 Correct 13 ms 17024 KB Output is correct
3 Correct 13 ms 17076 KB Output is correct
4 Correct 13 ms 17024 KB Output is correct
5 Correct 13 ms 17024 KB Output is correct
6 Correct 13 ms 17024 KB Output is correct
7 Correct 13 ms 17024 KB Output is correct
8 Correct 13 ms 17024 KB Output is correct
9 Correct 13 ms 17024 KB Output is correct
10 Correct 20 ms 18304 KB Output is correct
11 Correct 20 ms 18304 KB Output is correct
12 Correct 20 ms 18560 KB Output is correct
13 Correct 21 ms 18176 KB Output is correct
14 Correct 20 ms 18176 KB Output is correct
15 Correct 22 ms 18432 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 142700 KB Output is correct
2 Correct 978 ms 101096 KB Output is correct
3 Correct 945 ms 105632 KB Output is correct
4 Correct 1002 ms 113912 KB Output is correct
5 Correct 1043 ms 123752 KB Output is correct
6 Correct 1179 ms 130408 KB Output is correct
7 Correct 1106 ms 152680 KB Output is correct
8 Correct 854 ms 109420 KB Output is correct
9 Correct 552 ms 114156 KB Output is correct
10 Correct 567 ms 122216 KB Output is correct
11 Correct 615 ms 123624 KB Output is correct
12 Correct 708 ms 131048 KB Output is correct
13 Correct 956 ms 111612 KB Output is correct
14 Correct 958 ms 111368 KB Output is correct
15 Correct 951 ms 111424 KB Output is correct
16 Correct 994 ms 111336 KB Output is correct
17 Correct 1135 ms 151924 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17024 KB Output is correct
2 Correct 13 ms 17024 KB Output is correct
3 Correct 13 ms 17076 KB Output is correct
4 Correct 13 ms 17024 KB Output is correct
5 Correct 13 ms 17024 KB Output is correct
6 Correct 13 ms 17024 KB Output is correct
7 Correct 13 ms 17024 KB Output is correct
8 Correct 13 ms 17024 KB Output is correct
9 Correct 13 ms 17024 KB Output is correct
10 Correct 20 ms 18304 KB Output is correct
11 Correct 20 ms 18304 KB Output is correct
12 Correct 20 ms 18560 KB Output is correct
13 Correct 21 ms 18176 KB Output is correct
14 Correct 20 ms 18176 KB Output is correct
15 Correct 22 ms 18432 KB Output is correct
16 Correct 1206 ms 142700 KB Output is correct
17 Correct 978 ms 101096 KB Output is correct
18 Correct 945 ms 105632 KB Output is correct
19 Correct 1002 ms 113912 KB Output is correct
20 Correct 1043 ms 123752 KB Output is correct
21 Correct 1179 ms 130408 KB Output is correct
22 Correct 1106 ms 152680 KB Output is correct
23 Correct 854 ms 109420 KB Output is correct
24 Correct 552 ms 114156 KB Output is correct
25 Correct 567 ms 122216 KB Output is correct
26 Correct 615 ms 123624 KB Output is correct
27 Correct 708 ms 131048 KB Output is correct
28 Correct 956 ms 111612 KB Output is correct
29 Correct 958 ms 111368 KB Output is correct
30 Correct 951 ms 111424 KB Output is correct
31 Correct 994 ms 111336 KB Output is correct
32 Correct 1135 ms 151924 KB Output is correct
33 Correct 1244 ms 121036 KB Output is correct
34 Correct 428 ms 55652 KB Output is correct
35 Correct 1250 ms 114968 KB Output is correct
36 Correct 1166 ms 123940 KB Output is correct
37 Correct 1202 ms 115048 KB Output is correct
38 Correct 1197 ms 120808 KB Output is correct
39 Correct 1153 ms 103916 KB Output is correct
40 Correct 1072 ms 124980 KB Output is correct
41 Correct 832 ms 115816 KB Output is correct
42 Correct 736 ms 123368 KB Output is correct
43 Correct 1124 ms 117728 KB Output is correct
44 Correct 996 ms 115568 KB Output is correct
45 Correct 672 ms 104936 KB Output is correct
46 Correct 681 ms 103912 KB Output is correct
47 Correct 942 ms 111608 KB Output is correct
48 Correct 1018 ms 111336 KB Output is correct
49 Correct 993 ms 111588 KB Output is correct
50 Correct 978 ms 111512 KB Output is correct
51 Correct 907 ms 124384 KB Output is correct
52 Correct 897 ms 124512 KB Output is correct