oj.uz

Submission #163703

# Submission time Handle Problem Language Result Execution time Memory
163703 2019-11-14T17:28:58 Z dolphingarlic Werewolf (IOI18_werewolf) C++14
100 / 100
 1493 ms 141180 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<int> dsu_tree[2][200000], graph[200000];
int N, p[2][20][200000], timer, cmp[2][200000], order[2][200000];
pair<int, int> bounds[2][200000];

void dfs(int node, int t) {
    bounds[t][node] = {timer, timer};
    order[t][timer] = node;
    timer++;

    FOR(i, 1, 20) {
        if (p[t][i - 1][node] == -1) break;
        p[t][i][node] = p[t][i - 1][p[t][i - 1][node]];
    }

    for (int i : dsu_tree[t][node]) {
        p[t][0][i] = node;
        dfs(i, t);
        bounds[t][node].second =
            max(bounds[t][node].second, bounds[t][i].second);
    }
}

int find(int a, int t) {
    while (a != cmp[t][a]) cmp[t][a] = cmp[t][cmp[t][a]], a = cmp[t][a];
    return a;
}
void onion(int a, int b, int t) {
    cmp[t][find(a, t)] = cmp[t][find(b, t)];
}

vector<int> segtree[800000];
void build(int node = 1, int l = 0, int r = N - 1) {
    if (l == r) segtree[node] = {bounds[0][order[1][l]].first};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        
        int lptr = 0, rptr = 0;
        int lsz = segtree[node * 2].size(), rsz = segtree[node * 2 + 1].size();
        while (lptr < lsz && rptr < rsz) {
            if (segtree[node * 2][lptr] < segtree[node * 2 + 1][rptr]) {
                segtree[node].push_back(segtree[node * 2][lptr++]);
            } else {
                segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
            }
        }
        while (lptr < lsz) segtree[node].push_back(segtree[node * 2][lptr++]);
        while (rptr < rsz) segtree[node].push_back(segtree[node * 2 + 1][rptr++]);
    }
}

bool query(int a, int b, int x, int y, int node = 1, int l = 0, int r = N - 1) {
    if (r < a || l > b) return false;
    if (r <= b && l >= a)
        return (
            upper_bound(segtree[node].begin(), segtree[node].end(), y) -
                lower_bound(segtree[node].begin(), segtree[node].end(), x) !=
            0);
    int mid = (l + r) / 2;
    return (query(a, b, x, y, node * 2, l, mid) ||
            query(a, b, x, y, node * 2 + 1, mid + 1, r));
}

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;
    int Q = S.size();
    vector<int> A(Q);

    FOR(i, 0, N) cmp[0][i] = cmp[1][i] = i;
    FOR(i, 0, X.size()) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    for (int i = N - 1; ~i; i--)
        for (int j : graph[i])
            if (j > i && find(j, 0) != find(i, 0)) {
                dsu_tree[0][i].push_back(find(j, 0));
                onion(j, i, 0);
            }
    for (int i = 0; i < N; i++)
        for (int j : graph[i])
            if (j < i && find(j, 1) != find(i, 1)) {
                dsu_tree[1][i].push_back(find(j, 1));
                onion(j, i, 1);
            }

    memset(p, -1, sizeof(p));

    timer = 0;
    dfs(0, 0);
    timer = 0;
    dfs(N - 1, 1);

    build();

    FOR(i, 0, Q) {
        int X = S[i], Y = E[i];
        for (int j = 19; ~j; j--) {
            if (~p[0][j][X] && p[0][j][X] >= L[i]) X = p[0][j][X];
            if (~p[1][j][Y] && p[1][j][Y] <= R[i]) Y = p[1][j][Y];
        }
        A[i] = query(bounds[1][Y].first, bounds[1][Y].second, bounds[0][X].first, bounds[0][X].second);
    }

    return A;
}

Compilation message

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:3:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
werewolf.cpp:78:9:
     FOR(i, 0, X.size()) {
         ~~~~~~~~~~~~~~                  
werewolf.cpp:78:5: note: in expansion of macro 'FOR'
     FOR(i, 0, X.size()) {
     ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 59 ms 64604 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 67 ms 64632 KB Output is correct
5 Correct 60 ms 64504 KB Output is correct
6 Correct 60 ms 64632 KB Output is correct
7 Correct 59 ms 64504 KB Output is correct
8 Correct 60 ms 64632 KB Output is correct
9 Correct 61 ms 64632 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 59 ms 64604 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 67 ms 64632 KB Output is correct
5 Correct 60 ms 64504 KB Output is correct
6 Correct 60 ms 64632 KB Output is correct
7 Correct 59 ms 64504 KB Output is correct
8 Correct 60 ms 64632 KB Output is correct
9 Correct 61 ms 64632 KB Output is correct
10 Correct 68 ms 65532 KB Output is correct
11 Correct 79 ms 65480 KB Output is correct
12 Correct 74 ms 65400 KB Output is correct
13 Correct 75 ms 65660 KB Output is correct
14 Correct 68 ms 65656 KB Output is correct
15 Correct 76 ms 65528 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 127184 KB Output is correct
2 Correct 1063 ms 128996 KB Output is correct
3 Correct 924 ms 125296 KB Output is correct
4 Correct 1000 ms 123632 KB Output is correct
5 Correct 1068 ms 123504 KB Output is correct
6 Correct 1148 ms 123376 KB Output is correct
7 Correct 1070 ms 123376 KB Output is correct
8 Correct 954 ms 129136 KB Output is correct
9 Correct 833 ms 125360 KB Output is correct
10 Correct 659 ms 123760 KB Output is correct
11 Correct 733 ms 123504 KB Output is correct
12 Correct 894 ms 124240 KB Output is correct
13 Correct 1188 ms 136304 KB Output is correct
14 Correct 1153 ms 136048 KB Output is correct
15 Correct 1154 ms 136004 KB Output is correct
16 Correct 1136 ms 136032 KB Output is correct
17 Correct 1071 ms 124052 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 59 ms 64604 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 67 ms 64632 KB Output is correct
5 Correct 60 ms 64504 KB Output is correct
6 Correct 60 ms 64632 KB Output is correct
7 Correct 59 ms 64504 KB Output is correct
8 Correct 60 ms 64632 KB Output is correct
9 Correct 61 ms 64632 KB Output is correct
10 Correct 68 ms 65532 KB Output is correct
11 Correct 79 ms 65480 KB Output is correct
12 Correct 74 ms 65400 KB Output is correct
13 Correct 75 ms 65660 KB Output is correct
14 Correct 68 ms 65656 KB Output is correct
15 Correct 76 ms 65528 KB Output is correct
16 Correct 1071 ms 127184 KB Output is correct
17 Correct 1063 ms 128996 KB Output is correct
18 Correct 924 ms 125296 KB Output is correct
19 Correct 1000 ms 123632 KB Output is correct
20 Correct 1068 ms 123504 KB Output is correct
21 Correct 1148 ms 123376 KB Output is correct
22 Correct 1070 ms 123376 KB Output is correct
23 Correct 954 ms 129136 KB Output is correct
24 Correct 833 ms 125360 KB Output is correct
25 Correct 659 ms 123760 KB Output is correct
26 Correct 733 ms 123504 KB Output is correct
27 Correct 894 ms 124240 KB Output is correct
28 Correct 1188 ms 136304 KB Output is correct
29 Correct 1153 ms 136048 KB Output is correct
30 Correct 1154 ms 136004 KB Output is correct
31 Correct 1136 ms 136032 KB Output is correct
32 Correct 1071 ms 124052 KB Output is correct
33 Correct 1399 ms 125036 KB Output is correct
34 Correct 427 ms 85212 KB Output is correct
35 Correct 1422 ms 128736 KB Output is correct
36 Correct 1324 ms 125040 KB Output is correct
37 Correct 1493 ms 127652 KB Output is correct
38 Correct 1357 ms 125900 KB Output is correct
39 Correct 1486 ms 141180 KB Output is correct
40 Correct 1233 ms 133176 KB Output is correct
41 Correct 1072 ms 127096 KB Output is correct
42 Correct 769 ms 125168 KB Output is correct
43 Correct 1167 ms 133876 KB Output is correct
44 Correct 1285 ms 127860 KB Output is correct
45 Correct 1059 ms 140904 KB Output is correct
46 Correct 1040 ms 140784 KB Output is correct
47 Correct 1239 ms 135920 KB Output is correct
48 Correct 1181 ms 135872 KB Output is correct
49 Correct 1151 ms 135800 KB Output is correct
50 Correct 1181 ms 135612 KB Output is correct
51 Correct 1220 ms 132576 KB Output is correct
52 Correct 1174 ms 132308 KB Output is correct