oj.uz

Submission #555812

# Submission time Handle Problem Language Result Execution time Memory
555812 2022-05-01T15:14:29 Z cheissmart Werewolf (IOI18_werewolf) C++14
100 / 100
 1108 ms 196160 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int p1[N], jump1[N], time1[N], l1[N], r1[N];
vi T1[N];
int st1[N][20];
int find1(int u) {
    return jump1[u] == u ? u : jump1[u] = find1(jump1[u]);
}

int p2[N], jump2[N], time2[N], l2[N], r2[N];
vi T2[N];
int st2[N][20];
int find2(int u) {
    return jump2[u] == u ? u : jump2[u] = find2(jump2[u]);
}

int bit[N];
void add(int pos, int val) {
    pos++;
    for(; pos < N; pos += pos & -pos)
        bit[pos] += val;
}
int qry(int pos) {
    pos++;
    int res = 0;
    for(; pos; pos -= pos & -pos)
        res += bit[pos];
    return res;
}


vi check_validity(int n, vi a, vi b, vi S, vi E, vi L, vi R) {
    int m = SZ(a), q = SZ(S);
    V<vi> G(n);
    for(int i = 0; i < m; i++) {
        G[a[i]].PB(b[i]);
        G[b[i]].PB(a[i]);
    }
    int rt1, rt2;
    {
        int cnt = n;
        for(int i = 0; i < n; i++) {
            time1[i] = jump1[i] = p1[i] = i;
            for(int j:G[i]) if(j < i) {
                int x = find1(j), y = find1(i);
                if(x == y) continue;
                jump1[x] = jump1[y] = p1[x] = p1[y] = cnt;
                T1[cnt].PB(x), T1[cnt].PB(y);
                p1[cnt] = jump1[cnt] = cnt;
                time1[cnt] = i;
                cnt++;
            }
        }
        rt1 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st1[i][0] = p1[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st1[i][j] = st1[st1[i][j - 1]][j - 1];
    }
    {
        int cnt = n;
        for(int i = n - 1; i >= 0; i--) {
            time2[i] = jump2[i] = p2[i] = i;
            for(int j:G[i]) if(j > i) {
                int x = find2(j), y = find2(i);
                if(x == y) continue;
                jump2[x] = jump2[y] = p2[x] = p2[y] = cnt;
                T2[cnt].PB(x), T2[cnt].PB(y);
                p2[cnt] = jump2[cnt] = cnt;
                time2[cnt] = i;
                cnt++;
            }
        }
        rt2 = cnt - 1;
        for(int i = 0; i < cnt; i++)
            st2[i][0] = p2[i];
        for(int j = 1; j < 20; j++)
            for(int i = 0; i < cnt; i++)
                st2[i][j] = st2[st2[i][j - 1]][j - 1];
    }

    vi order1;
    {
        function<void(int)> dfs = [&] (int u) {
            l1[u] = SZ(order1);
            if(T1[u].empty()) {
                assert(0 <= u && u < n);
                order1.PB(u);
            }
            for(int v:T1[u])
                dfs(v);
            r1[u] = SZ(order1);
        };
        dfs(rt1);
    }
    vi pos(n);
    for(int i = 0; i < n; i++)
        pos[order1[i]] = i;

    vi order2;
    {
        function<void(int)> dfs = [&] (int u) {
            l2[u] = SZ(order2);
            if(T2[u].empty()) {
                assert(0 <= u && u < n);
                order2.PB(pos[u]);
            }
            for(int v:T2[u])
                dfs(v);
            r2[u] = SZ(order2);
        };
        dfs(rt2);
    }
    vi ans(q);
    V<V<array<int, 3>>> ev(n);
    for(int i = 0; i < q; i++) {
        int e = E[i], s = S[i], l = L[i], r = R[i];
        for(int j = 19; j >= 0; j--) {
            if(time1[st1[e][j]] <= r) {
                e = st1[e][j];
            }
        }
        for(int j = 19; j >= 0; j--) {
            if(time2[st2[s][j]] >= l) {
                s = st2[s][j];
            }
        }
        int lb = l1[e], rb = r1[e];
        if(l2[s]) ev[l2[s] - 1].PB({i, rb, lb});
        ev[r2[s] - 1].PB({i, lb, rb});
    }
    for(int i = 0; i < n; i++) {
        add(order2[i], 1);
        for(auto[qid, l, r]:ev[i]) {
            if(l < r) {
                ans[qid] += qry(r - 1) - qry(l - 1);
            } else {
                swap(l, r);
                ans[qid] -= qry(r - 1) - qry(l - 1);
            }
        }
    }
    for(int i = 0; i < q; i++)
        ans[i] = ans[i] > 0;
    return ans;
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:153:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |         for(auto[qid, l, r]:ev[i]) {
      |                 ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47484 KB Output is correct
2 Correct 26 ms 47444 KB Output is correct
3 Correct 22 ms 47416 KB Output is correct
4 Correct 23 ms 47392 KB Output is correct
5 Correct 23 ms 47444 KB Output is correct
6 Correct 23 ms 47460 KB Output is correct
7 Correct 23 ms 47460 KB Output is correct
8 Correct 23 ms 47460 KB Output is correct
9 Correct 23 ms 47460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47484 KB Output is correct
2 Correct 26 ms 47444 KB Output is correct
3 Correct 22 ms 47416 KB Output is correct
4 Correct 23 ms 47392 KB Output is correct
5 Correct 23 ms 47444 KB Output is correct
6 Correct 23 ms 47460 KB Output is correct
7 Correct 23 ms 47460 KB Output is correct
8 Correct 23 ms 47460 KB Output is correct
9 Correct 23 ms 47460 KB Output is correct
10 Correct 29 ms 49368 KB Output is correct
11 Correct 28 ms 49364 KB Output is correct
12 Correct 27 ms 49304 KB Output is correct
13 Correct 29 ms 49496 KB Output is correct
14 Correct 29 ms 49404 KB Output is correct
15 Correct 29 ms 49364 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 174912 KB Output is correct
2 Correct 831 ms 180496 KB Output is correct
3 Correct 708 ms 176164 KB Output is correct
4 Correct 682 ms 173792 KB Output is correct
5 Correct 696 ms 173960 KB Output is correct
6 Correct 763 ms 174684 KB Output is correct
7 Correct 703 ms 173192 KB Output is correct
8 Correct 761 ms 188992 KB Output is correct
9 Correct 582 ms 182232 KB Output is correct
10 Correct 556 ms 181916 KB Output is correct
11 Correct 560 ms 181952 KB Output is correct
12 Correct 563 ms 181964 KB Output is correct
13 Correct 910 ms 188344 KB Output is correct
14 Correct 928 ms 188292 KB Output is correct
15 Correct 887 ms 188324 KB Output is correct
16 Correct 892 ms 188344 KB Output is correct
17 Correct 698 ms 181264 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47484 KB Output is correct
2 Correct 26 ms 47444 KB Output is correct
3 Correct 22 ms 47416 KB Output is correct
4 Correct 23 ms 47392 KB Output is correct
5 Correct 23 ms 47444 KB Output is correct
6 Correct 23 ms 47460 KB Output is correct
7 Correct 23 ms 47460 KB Output is correct
8 Correct 23 ms 47460 KB Output is correct
9 Correct 23 ms 47460 KB Output is correct
10 Correct 29 ms 49368 KB Output is correct
11 Correct 28 ms 49364 KB Output is correct
12 Correct 27 ms 49304 KB Output is correct
13 Correct 29 ms 49496 KB Output is correct
14 Correct 29 ms 49404 KB Output is correct
15 Correct 29 ms 49364 KB Output is correct
16 Correct 788 ms 174912 KB Output is correct
17 Correct 831 ms 180496 KB Output is correct
18 Correct 708 ms 176164 KB Output is correct
19 Correct 682 ms 173792 KB Output is correct
20 Correct 696 ms 173960 KB Output is correct
21 Correct 763 ms 174684 KB Output is correct
22 Correct 703 ms 173192 KB Output is correct
23 Correct 761 ms 188992 KB Output is correct
24 Correct 582 ms 182232 KB Output is correct
25 Correct 556 ms 181916 KB Output is correct
26 Correct 560 ms 181952 KB Output is correct
27 Correct 563 ms 181964 KB Output is correct
28 Correct 910 ms 188344 KB Output is correct
29 Correct 928 ms 188292 KB Output is correct
30 Correct 887 ms 188324 KB Output is correct
31 Correct 892 ms 188344 KB Output is correct
32 Correct 698 ms 181264 KB Output is correct
33 Correct 900 ms 185004 KB Output is correct
34 Correct 288 ms 82540 KB Output is correct
35 Correct 960 ms 189304 KB Output is correct
36 Correct 854 ms 184364 KB Output is correct
37 Correct 968 ms 188540 KB Output is correct
38 Correct 877 ms 185276 KB Output is correct
39 Correct 929 ms 196160 KB Output is correct
40 Correct 1022 ms 191516 KB Output is correct
41 Correct 869 ms 186416 KB Output is correct
42 Correct 669 ms 179872 KB Output is correct
43 Correct 1108 ms 192980 KB Output is correct
44 Correct 1059 ms 187828 KB Output is correct
45 Correct 771 ms 195432 KB Output is correct
46 Correct 811 ms 194940 KB Output is correct
47 Correct 1069 ms 187288 KB Output is correct
48 Correct 1000 ms 187128 KB Output is correct
49 Correct 1033 ms 188436 KB Output is correct
50 Correct 1025 ms 187168 KB Output is correct
51 Correct 854 ms 193208 KB Output is correct
52 Correct 865 ms 193236 KB Output is correct