oj.uz

Submission #502278

# Submission time Handle Problem Language Result Execution time Memory
502278 2022-01-05T17:01:53 Z MilosMilutinovic Werewolf (IOI18_werewolf) C++14
100 / 100
 1328 ms 156004 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MX = 200001;
const int LG = 25;

int n, par[MX][2], fs[MX][LG], fe[MX][LG];
vector<int> adj[MX], e[MX][2];
vector<pair<int, int>> ed;

struct DSU {
    int fa[MX];
    void init() { iota(fa, fa + MX, 0); }
    DSU() { init(); }
    int root(int x) { return fa[x] == x ? x : fa[x] = root(fa[x]); }
    void unite(int x, int y) { fa[root(x)] = root(y); }
};

void BuildSmall() {
    // 0 is root
    vector<int> fa(n), sz(n), mn(n);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        sz[i] = 1;
        mn[i] = i;
    }
    struct op {
        int root_a;
        int root_b;
        int sz_a;
        int sz_b;
        int mn_a;
        int mn_b;
    };
    stack<op> stk;
    function<int(int)> root = [&](int x) {
        return fa[x] == x ? x : root(fa[x]);
    };
    function<void(int, int)> unite = [&](int x, int y) {
        x = root(x);
        y = root(y);
        if (sz[x] < sz[y]) swap(x, y);
        stk.push({x, y, sz[x], sz[y], mn[x], mn[y]});
        if (x == y) return;
        fa[y] = x;
        sz[x] += sz[y];
        mn[x] = min(mn[x], mn[y]);
    };
    function<void()> roll = [&]() {
        op lst = stk.top();
        stk.pop();
        fa[lst.root_a] = lst.root_a;
        fa[lst.root_b] = lst.root_b;
        sz[lst.root_a] = lst.sz_a;
        sz[lst.root_b] = lst.sz_b;
        mn[lst.root_a] = lst.mn_a;
        mn[lst.root_b] = lst.mn_b;
    };
    sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
        return min(x.first, x.second) < min(y.first, y.second);
    });
    for (int i = ed.size() - 1; i >= 0; i--) {
        unite(ed[i].first, ed[i].second);
    }
    for (int i = 1; i < n; i++)
        par[i][0] = -1;
    int ptr = 0;
    for (int i = 0; i < n; i++) {
        while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
            roll();
            ptr++;
        }
        for (int j : adj[i]) {
            int oth = mn[root(j)];
            if (par[oth][0] == -1) par[oth][0] = i;
        }
    }
}

void BuildLarge() {
    // n-1 is root
    vector<int> fa(n), sz(n), mx(n);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        sz[i] = 1;
        mx[i] = i;
    }
    struct op {
        int root_a;
        int root_b;
        int sz_a;
        int sz_b;
        int mx_a;
        int mx_b;
    };
    stack<op> stk;
    function<int(int)> root = [&](int x) {
        return fa[x] == x ? x : root(fa[x]);
    };
    function<void(int, int)> unite = [&](int x, int y) {
        x = root(x);
        y = root(y);
        if (sz[x] < sz[y]) swap(x, y);
        stk.push({x, y, sz[x], sz[y], mx[x], mx[y]});
        if (x == y) return;
        fa[y] = x;
        sz[x] += sz[y];
        mx[x] = max(mx[x], mx[y]);
    };
    function<void()> roll = [&]() {
        op lst = stk.top();
        stk.pop();
        fa[lst.root_a] = lst.root_a;
        fa[lst.root_b] = lst.root_b;
        sz[lst.root_a] = lst.sz_a;
        sz[lst.root_b] = lst.sz_b;
        mx[lst.root_a] = lst.mx_a;
        mx[lst.root_b] = lst.mx_b;
    };
    sort(ed.begin(), ed.end(), [&](pair<int, int> x, pair<int, int> y) {
        return max(x.first, x.second) > max(y.first, y.second);
    });
    for (int i = ed.size(); i >= 0; i--) {
        unite(ed[i].first, ed[i].second);
    }
    for (int i = 0; i < n - 1; i++)
        par[i][1] = -1;
    par[n - 1][1] = n - 1;
    int ptr = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
            roll();
            ptr++;
        }
        for (int j : adj[i]) {
            int oth = mx[root(j)];
            if (par[oth][1] == -1) par[oth][1] = i;
        }
    }
}

int tin[MX][2], tout[MX][2], tajm[2];

void dfs(int u, int pa, int t) {
    tin[u][t] = ++tajm[t];
    for (int v : e[u][t])
        if (v != pa)
            dfs(v, u, t);
    tout[u][t] = tajm[t];
}

bool is_anc(int x, int y, int t) {
    return tin[x][t] <= tin[y][t] && tout[y][t] <= tout[x][t];
}

const int M = 20 * MX;

int root[MX], ls[M], rs[M], st[M], tsz;

void update(int& c, int p, int ss, int se, int qi) {
    c = ++tsz; ls[c] = ls[p]; rs[c] = rs[p]; st[c] = st[p] + 1;
    if (ss == se) return;
    int mid = ss + se >> 1;
    if (qi <= mid) update(ls[c], ls[p], ss, mid, qi);
    else update(rs[c], rs[p], mid + 1, se, qi);
}

int query(int c, int ss, int se, int qs, int qe) {
    if (ss > qe || se < qs) return 0;
    if (qs <= ss && se <= qe) return st[c];
    int mid = ss + se >> 1;
    return query(ls[c], ss, mid, qs, qe) + query(rs[c], mid + 1, se, qs, qe);
}

void walk(int c, int ss, int se) {
    if (ss == se) {
        cout << st[c] << " ";
        return;
    }
    int mid = ss + se >> 1;
    walk(ls[c], ss, mid);
    walk(rs[c], mid + 1, se);
}

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 M = X.size();
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
        ed.emplace_back(X[i], Y[i]);
    }
    BuildSmall();
    BuildLarge();
    /*puts("Small parent");
    for (int i = 0; i < n; i++) cout << par[i][0] << " ";
    puts("Large parent");
    for (int i = 0; i < n; i++) cout << par[i][1] << " ";*/
    for (int i = 1; i < n; i++) {
        e[par[i][0]][0].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        e[par[i][1]][1].push_back(i);
    }
    dfs(0, 0, 0);
    dfs(n - 1, n - 1, 1);
    for (int i = 0; i < n; i++)
        fs[i][0] = par[i][0];
    for (int i = 0; i < n; i++)
        fe[i][0] = par[i][1];
    for (int j = 1; j < LG; j++) {
        for (int i = 0; i < n; i++) {
            fs[i][j] = fs[fs[i][j - 1]][j - 1];
            fe[i][j] = fe[fe[i][j - 1]][j - 1];
        }
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return tin[i][0] < tin[j][0];
    });
    //puts("order");
    for (int i = 1; i <= n; i++) {
    //    cout << ord[i - 1] << " ";
        assert(tin[ord[i - 1]][0] == i);
        update(root[i], root[i - 1], 1, n, tin[ord[i - 1]][1]);
    }
    /*puts("");
    for (int i = 1; i <= n; i++) {
        walk(root[i], 1, n);
        puts("");
    }*/
    int Q = S.size();
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int l = L[i];
        int r = R[i];
        int s = S[i];
        int e = E[i];
        for (int j = LG - 1; j >= 0; j--) {
            if (fs[s][j] >= l) s = fs[s][j];
            if (fe[e][j] <= r) e = fe[e][j];
        }
        int L0 = tin[s][0];
        int R0 = tout[s][0];
        int L1 = tin[e][1];
        int R1 = tout[e][1];
        int all = query(root[R0], 1, n, L1, R1);
        int rem = query(root[L0 - 1], 1, n, L1, R1);
        assert(all >= rem);
        if (all > rem) ans[i] = 1;
    }
    return ans;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Compilation message

werewolf.cpp: In function 'void BuildSmall()':
werewolf.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (ptr < ed.size() && min(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void BuildLarge()':
werewolf.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         while (ptr < ed.size() && max(ed[ptr].first, ed[ptr].second) == i) {
      |                ~~~~^~~~~~~~~~~
werewolf.cpp: In function 'void update(int&, int, int, int, int)':
werewolf.cpp:165:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  165 |     int mid = ss + se >> 1;
      |               ~~~^~~~
werewolf.cpp: In function 'int query(int, int, int, int, int)':
werewolf.cpp:173:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |     int mid = ss + se >> 1;
      |               ~~~^~~~
werewolf.cpp: In function 'void walk(int, int, int)':
werewolf.cpp:182:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |     int mid = ss + se >> 1;
      |               ~~~^~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 14 ms 15960 KB Output is correct
12 Correct 15 ms 15972 KB Output is correct
13 Correct 17 ms 16164 KB Output is correct
14 Correct 14 ms 16224 KB Output is correct
15 Correct 17 ms 16152 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 130152 KB Output is correct
2 Correct 982 ms 144248 KB Output is correct
3 Correct 935 ms 140512 KB Output is correct
4 Correct 831 ms 138848 KB Output is correct
5 Correct 819 ms 139012 KB Output is correct
6 Correct 859 ms 138648 KB Output is correct
7 Correct 814 ms 138480 KB Output is correct
8 Correct 947 ms 144260 KB Output is correct
9 Correct 742 ms 140588 KB Output is correct
10 Correct 583 ms 138784 KB Output is correct
11 Correct 648 ms 138736 KB Output is correct
12 Correct 687 ms 138640 KB Output is correct
13 Correct 952 ms 150488 KB Output is correct
14 Correct 932 ms 150532 KB Output is correct
15 Correct 931 ms 150540 KB Output is correct
16 Correct 885 ms 150524 KB Output is correct
17 Correct 745 ms 138480 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 7 ms 14412 KB Output is correct
6 Correct 7 ms 14412 KB Output is correct
7 Correct 7 ms 14412 KB Output is correct
8 Correct 7 ms 14412 KB Output is correct
9 Correct 7 ms 14412 KB Output is correct
10 Correct 13 ms 15948 KB Output is correct
11 Correct 14 ms 15960 KB Output is correct
12 Correct 15 ms 15972 KB Output is correct
13 Correct 17 ms 16164 KB Output is correct
14 Correct 14 ms 16224 KB Output is correct
15 Correct 17 ms 16152 KB Output is correct
16 Correct 833 ms 130152 KB Output is correct
17 Correct 982 ms 144248 KB Output is correct
18 Correct 935 ms 140512 KB Output is correct
19 Correct 831 ms 138848 KB Output is correct
20 Correct 819 ms 139012 KB Output is correct
21 Correct 859 ms 138648 KB Output is correct
22 Correct 814 ms 138480 KB Output is correct
23 Correct 947 ms 144260 KB Output is correct
24 Correct 742 ms 140588 KB Output is correct
25 Correct 583 ms 138784 KB Output is correct
26 Correct 648 ms 138736 KB Output is correct
27 Correct 687 ms 138640 KB Output is correct
28 Correct 952 ms 150488 KB Output is correct
29 Correct 932 ms 150532 KB Output is correct
30 Correct 931 ms 150540 KB Output is correct
31 Correct 885 ms 150524 KB Output is correct
32 Correct 745 ms 138480 KB Output is correct
33 Correct 1075 ms 139456 KB Output is correct
34 Correct 379 ms 57764 KB Output is correct
35 Correct 1270 ms 143728 KB Output is correct
36 Correct 1055 ms 139660 KB Output is correct
37 Correct 1272 ms 142448 KB Output is correct
38 Correct 1143 ms 140644 KB Output is correct
39 Correct 1097 ms 155644 KB Output is correct
40 Correct 994 ms 153952 KB Output is correct
41 Correct 920 ms 141568 KB Output is correct
42 Correct 706 ms 139672 KB Output is correct
43 Correct 1284 ms 150680 KB Output is correct
44 Correct 1328 ms 142420 KB Output is correct
45 Correct 988 ms 156004 KB Output is correct
46 Correct 981 ms 155608 KB Output is correct
47 Correct 980 ms 150724 KB Output is correct
48 Correct 936 ms 150420 KB Output is correct
49 Correct 989 ms 150720 KB Output is correct
50 Correct 985 ms 150508 KB Output is correct
51 Correct 983 ms 153932 KB Output is correct
52 Correct 922 ms 153920 KB Output is correct