oj.uz

Submission #109022

# Submission time Handle Problem Language Result Execution time Memory
109022 2019-05-04T04:41:26 Z PeppaPig Werewolf (IOI18_werewolf) C++14
100 / 100
 2494 ms 220804 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int n, m, q;

struct node {
    int d;
    node *l, *r;
    node(int d, node *l, node *r) : d(d), l(l), r(r) { }
};

node* newleaf(int d) { return new node(d, nullptr, nullptr); }
node* newpar(node *l, node *r) { return new node(l->d + r->d, l, r); }

node* build(int l = 1, int r = n) {
    if(l == r) return newleaf(0);
    int mid = (l + r) >> 1;
    return newpar(build(l, mid), build(mid+1, r));
}

node* update(node *p, int x, int l = 1, int r = n) {
    if(l == r) return newleaf(p->d + 1);
    int mid = (l + r) >> 1;
    if(x <= mid) return newpar(update(p->l, x, l, mid), p->r);
    else return newpar(p->l, update(p->r, x, mid+1, r));
}

int query(node *pl, node *pr, int x, int y, int l = 1, int r = n) {
    if(x > r || l > y) return 0;
    if(x <= l && r <= y) return pr->d - pl->d;
    int mid = (l + r) >> 1;
    return query(pl->l, pr->l, x, y, l, mid) + query(pl->r, pr->r, x, y, mid+1, r);
}

node* t[N];

int dsu[N], hpar[N][18], wpar[N][18];
int hin[N], hout[N], hpos[N];
int win[N], wout[N], wpos[N];
vector<int> g[N], hg[N], wg[N];

int find(int x) { return dsu[x] = x == dsu[x] ? x : find(dsu[x]); }

void gen_human(int u, int p) {
    static int hidx = 0;
    hin[u] = ++hidx, hpos[hidx] = u;
    hpar[u][0] = p;
    for(int i = 1; i <= 17; i++) hpar[u][i] = hpar[hpar[u][i-1]][i-1];
    for(int v : hg[u]) if(v != p) gen_human(v, u);
    hout[u] = hidx;
}

void gen_werewolf(int u, int p) {
    static int widx = 0;
    win[u] = ++widx, wpos[widx] = u;
    wpar[u][0] = p;
    for(int i = 1; i <= 17; i++) wpar[u][i] = wpar[wpar[u][i-1]][i-1];
    for(int v : wg[u]) if(v != p) gen_werewolf(v, u);
    wout[u] = widx;
}

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, m = X.size(), q = S.size();

    for(int i = 0; i < m; i++) {
        g[X[i]+1].emplace_back(Y[i]+1);
        g[Y[i]+1].emplace_back(X[i]+1);
    }
    iota(dsu, dsu+N, 0);
    for(int u = n; u; u--) for(int v : g[u]) if(v > u) {
        int pv = find(v);
        if(pv == u) continue;
        hg[u].emplace_back(pv), hg[pv].emplace_back(u);
        dsu[pv] = u;
    }
    iota(dsu, dsu+N, 0);
    for(int u = 1; u <= n; u++) for(int v : g[u]) if(v < u) {
        int pv = find(v);
        if(pv == u) continue;
        wg[u].emplace_back(pv), wg[pv].emplace_back(u);
        dsu[pv] = u;
    }

    gen_human(1, 0), gen_werewolf(n, 0);
    t[0] = build();
    for(int i = 1; i <= n; i++) t[i] = update(t[i-1], win[hpos[i]]);

    vector<int> ret;
    for(int T = 0; T < q; T++) {
        int s = S[T]+1, e = E[T]+1;
        for(int i = 17; ~i; i--) if(hpar[s][i] && hpar[s][i] >= L[T]+1) s = hpar[s][i];
        for(int i = 17; ~i; i--) if(wpar[e][i] && wpar[e][i] <= R[T]+1) e = wpar[e][i];
        if(query(t[hin[s]-1], t[hout[s]], win[e], wout[e])) ret.emplace_back(1);
        else ret.emplace_back(0);
    }

    return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15360 KB Output is correct
2 Correct 17 ms 15360 KB Output is correct
3 Correct 18 ms 15224 KB Output is correct
4 Correct 16 ms 15232 KB Output is correct
5 Correct 16 ms 15360 KB Output is correct
6 Correct 16 ms 15360 KB Output is correct
7 Correct 18 ms 15360 KB Output is correct
8 Correct 16 ms 15232 KB Output is correct
9 Correct 16 ms 15304 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15360 KB Output is correct
2 Correct 17 ms 15360 KB Output is correct
3 Correct 18 ms 15224 KB Output is correct
4 Correct 16 ms 15232 KB Output is correct
5 Correct 16 ms 15360 KB Output is correct
6 Correct 16 ms 15360 KB Output is correct
7 Correct 18 ms 15360 KB Output is correct
8 Correct 16 ms 15232 KB Output is correct
9 Correct 16 ms 15304 KB Output is correct
10 Correct 27 ms 17664 KB Output is correct
11 Correct 30 ms 17756 KB Output is correct
12 Correct 26 ms 17664 KB Output is correct
13 Correct 26 ms 17920 KB Output is correct
14 Correct 28 ms 17784 KB Output is correct
15 Correct 30 ms 17784 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 211120 KB Output is correct
2 Correct 1663 ms 214344 KB Output is correct
3 Correct 1448 ms 212104 KB Output is correct
4 Correct 1301 ms 211188 KB Output is correct
5 Correct 1228 ms 211260 KB Output is correct
6 Correct 1520 ms 211100 KB Output is correct
7 Correct 1422 ms 211072 KB Output is correct
8 Correct 1734 ms 214492 KB Output is correct
9 Correct 1291 ms 212140 KB Output is correct
10 Correct 943 ms 211280 KB Output is correct
11 Correct 1027 ms 211188 KB Output is correct
12 Correct 1096 ms 211056 KB Output is correct
13 Correct 1488 ms 215560 KB Output is correct
14 Correct 1580 ms 215708 KB Output is correct
15 Correct 1541 ms 215840 KB Output is correct
16 Correct 1478 ms 215668 KB Output is correct
17 Correct 1237 ms 210940 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15360 KB Output is correct
2 Correct 17 ms 15360 KB Output is correct
3 Correct 18 ms 15224 KB Output is correct
4 Correct 16 ms 15232 KB Output is correct
5 Correct 16 ms 15360 KB Output is correct
6 Correct 16 ms 15360 KB Output is correct
7 Correct 18 ms 15360 KB Output is correct
8 Correct 16 ms 15232 KB Output is correct
9 Correct 16 ms 15304 KB Output is correct
10 Correct 27 ms 17664 KB Output is correct
11 Correct 30 ms 17756 KB Output is correct
12 Correct 26 ms 17664 KB Output is correct
13 Correct 26 ms 17920 KB Output is correct
14 Correct 28 ms 17784 KB Output is correct
15 Correct 30 ms 17784 KB Output is correct
16 Correct 1456 ms 211120 KB Output is correct
17 Correct 1663 ms 214344 KB Output is correct
18 Correct 1448 ms 212104 KB Output is correct
19 Correct 1301 ms 211188 KB Output is correct
20 Correct 1228 ms 211260 KB Output is correct
21 Correct 1520 ms 211100 KB Output is correct
22 Correct 1422 ms 211072 KB Output is correct
23 Correct 1734 ms 214492 KB Output is correct
24 Correct 1291 ms 212140 KB Output is correct
25 Correct 943 ms 211280 KB Output is correct
26 Correct 1027 ms 211188 KB Output is correct
27 Correct 1096 ms 211056 KB Output is correct
28 Correct 1488 ms 215560 KB Output is correct
29 Correct 1580 ms 215708 KB Output is correct
30 Correct 1541 ms 215840 KB Output is correct
31 Correct 1478 ms 215668 KB Output is correct
32 Correct 1237 ms 210940 KB Output is correct
33 Correct 1901 ms 212076 KB Output is correct
34 Correct 457 ms 37744 KB Output is correct
35 Correct 2367 ms 214256 KB Output is correct
36 Correct 1874 ms 211476 KB Output is correct
37 Correct 2262 ms 213928 KB Output is correct
38 Correct 1973 ms 211956 KB Output is correct
39 Correct 2093 ms 220804 KB Output is correct
40 Correct 1832 ms 217204 KB Output is correct
41 Correct 1926 ms 213184 KB Output is correct
42 Correct 1165 ms 211324 KB Output is correct
43 Correct 2494 ms 216912 KB Output is correct
44 Correct 2077 ms 213616 KB Output is correct
45 Correct 1712 ms 220768 KB Output is correct
46 Correct 1875 ms 220652 KB Output is correct
47 Correct 1457 ms 215404 KB Output is correct
48 Correct 1548 ms 215452 KB Output is correct
49 Correct 1667 ms 215440 KB Output is correct
50 Correct 1487 ms 215752 KB Output is correct
51 Correct 1679 ms 217812 KB Output is correct
52 Correct 1651 ms 217536 KB Output is correct