oj.uz

Submission #569010

# Submission time Handle Problem Language Result Execution time Memory
569010 2022-05-26T13:23:56 Z ngpin04 Werewolf (IOI18_werewolf) C++17
100 / 100
 1405 ms 173772 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct DSU {
    int n,node,timer;
    vector <int> par;
    vector <int> tin,tout;
    vector <vector <int>> adj;

    DSU(int _n = 0) {
        n = _n;
        par.assign(2 * n + 5, -1);
        adj.resize(2 * n + 5);
        tin.assign(2 * n + 5, 0);
        tout.assign(2 * n + 5, 0);
        node = n;
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
    }

    void join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return;
        adj[node].push_back(u);
        adj[node].push_back(v);
        par[u] = par[v] = node;
        node++;
    }    

    void dfs(int u) {
        // cerr << "dfs " << u << " " << timer << "\n";
        if (u < n) 
            tin[u] = ++timer;

        for (int v : adj[u]) {
            dfs(v);
            if (!tin[u])
                tin[u] = tin[v];
        }

        tout[u] = timer;
    }

    void build() {
        timer = 0;
        dfs(node - 1);
        for (int i = 0; i < node; i++)
            par[i] = -1;
        node = n;
    }

    pair <int, int> gettree(int u) {
        // cerr << "get tree " << u << " ";
        u = getpar(u);
        // cerr << u << " " << tin[u] << " " << tout[u] << "\n";
        return mp(tin[u], tout[u]);
    }
};

DSU pre, suf;

vector <int> st[N << 2];
vector <int> ed[N];
vector <int> qr[N];


pair <int, int> range[N][2];

int tin[N][2];
int ans[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,m,q;

void update(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos)
        return;
    st[id].push_back(val);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, pos, val);
    update(id << 1 | 1, mid + 1, r, pos, val);
}

void update(int pos, int val) {
    update(1, 1, n, pos, val);
}

int getans(int id, int l, int r, int u, int v, int x, int y) {
    if (l > v || r < u)
        return 0;
    if (l >= u && r <= v) {
        auto it = lower_bound(ALL(st[id]), x);
        return (it != st[id].end() && *it <= y);
    }
    int mid = (l + r) >> 1;
    int lnode = getans(id << 1, l, mid, u, v, x, y);
    int rnode = getans(id << 1 | 1, mid + 1, r, u, v, x, y);
    return lnode | rnode;
}

int getans(int l, int r, int x, int y) {
    return getans(1, 1, n, l, r, x, y);
}

void build() {
    pre = suf = DSU(n);
    for (int i = 0; i < m; i++) 
        if (x[i] > y[i])
            swap(x[i], y[i]);

    for (int i = 0; i < m; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    for (int i = 0; i < n; i++) 
    for (int j : ed[i])
        pre.join(i, j);
    
    pre.build();

    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) 
            range[ind][0] = pre.gettree(t[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][0] = pre.tin[i];

    // process suffix 
    for (int i = 0; i < n; i++)
        qr[i].clear(), ed[i].clear();

    for (int i = 0; i < m; i++)
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    for (int i = n - 1; i >= 0; i--) 
    for (int j : ed[i])
        suf.join(i, j);

    suf.build();

    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i]) 
            suf.join(i, j);

        for (int ind : qr[i]) 
            range[ind][1] = suf.gettree(s[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][1] = suf.tin[i];
}  

void solve() {
    for (int i = 0; i < n; i++)
        update(tin[i][0], tin[i][1]);

    for (int i = 1; i <= 4 * n; i++)
        sort(ALL(st[i]));

    for (int i = 0; i < q; i++) {
        auto [l, r] = range[i][0];
        auto [u, v] = range[i][1];
        // cerr << l << " " << r << " " << u << " " << v << "\n";
        ans[i] = getans(l, r, u, 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;
    m = X.size();
    for (int i = 0; i < m; i++)
        x[i] = X[i], y[i] = Y[i];

    q = S.size();
    for (int i = 0; i < q; i++) {
        s[i] = S[i];
        t[i] = E[i];
        l[i] = L[i];
        r[i] = R[i];
    }

    build();
    solve();
    vector <int> res;
    for (int i = 0; i < q; i++)
        res.push_back(ans[i]);
    return res;
}

//#include "grader.cpp"

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 56776 KB Output is correct
2 Correct 32 ms 56652 KB Output is correct
3 Correct 36 ms 56660 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 41 ms 56652 KB Output is correct
6 Correct 38 ms 56652 KB Output is correct
7 Correct 40 ms 56684 KB Output is correct
8 Correct 31 ms 56700 KB Output is correct
9 Correct 37 ms 56760 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 56776 KB Output is correct
2 Correct 32 ms 56652 KB Output is correct
3 Correct 36 ms 56660 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 41 ms 56652 KB Output is correct
6 Correct 38 ms 56652 KB Output is correct
7 Correct 40 ms 56684 KB Output is correct
8 Correct 31 ms 56700 KB Output is correct
9 Correct 37 ms 56760 KB Output is correct
10 Correct 46 ms 58308 KB Output is correct
11 Correct 41 ms 58236 KB Output is correct
12 Correct 41 ms 58188 KB Output is correct
13 Correct 42 ms 58328 KB Output is correct
14 Correct 39 ms 58364 KB Output is correct
15 Correct 46 ms 58400 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1349 ms 165552 KB Output is correct
2 Correct 1370 ms 168876 KB Output is correct
3 Correct 1148 ms 166704 KB Output is correct
4 Correct 1207 ms 165544 KB Output is correct
5 Correct 1232 ms 165668 KB Output is correct
6 Correct 1260 ms 165388 KB Output is correct
7 Correct 1281 ms 163996 KB Output is correct
8 Correct 1145 ms 168816 KB Output is correct
9 Correct 1020 ms 166060 KB Output is correct
10 Correct 842 ms 165108 KB Output is correct
11 Correct 982 ms 165208 KB Output is correct
12 Correct 1163 ms 165240 KB Output is correct
13 Correct 986 ms 168868 KB Output is correct
14 Correct 1039 ms 168940 KB Output is correct
15 Correct 876 ms 168980 KB Output is correct
16 Correct 856 ms 169016 KB Output is correct
17 Correct 1087 ms 164000 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 56776 KB Output is correct
2 Correct 32 ms 56652 KB Output is correct
3 Correct 36 ms 56660 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 41 ms 56652 KB Output is correct
6 Correct 38 ms 56652 KB Output is correct
7 Correct 40 ms 56684 KB Output is correct
8 Correct 31 ms 56700 KB Output is correct
9 Correct 37 ms 56760 KB Output is correct
10 Correct 46 ms 58308 KB Output is correct
11 Correct 41 ms 58236 KB Output is correct
12 Correct 41 ms 58188 KB Output is correct
13 Correct 42 ms 58328 KB Output is correct
14 Correct 39 ms 58364 KB Output is correct
15 Correct 46 ms 58400 KB Output is correct
16 Correct 1349 ms 165552 KB Output is correct
17 Correct 1370 ms 168876 KB Output is correct
18 Correct 1148 ms 166704 KB Output is correct
19 Correct 1207 ms 165544 KB Output is correct
20 Correct 1232 ms 165668 KB Output is correct
21 Correct 1260 ms 165388 KB Output is correct
22 Correct 1281 ms 163996 KB Output is correct
23 Correct 1145 ms 168816 KB Output is correct
24 Correct 1020 ms 166060 KB Output is correct
25 Correct 842 ms 165108 KB Output is correct
26 Correct 982 ms 165208 KB Output is correct
27 Correct 1163 ms 165240 KB Output is correct
28 Correct 986 ms 168868 KB Output is correct
29 Correct 1039 ms 168940 KB Output is correct
30 Correct 876 ms 168980 KB Output is correct
31 Correct 856 ms 169016 KB Output is correct
32 Correct 1087 ms 164000 KB Output is correct
33 Correct 1261 ms 166372 KB Output is correct
34 Correct 314 ms 97992 KB Output is correct
35 Correct 1349 ms 169148 KB Output is correct
36 Correct 1244 ms 166100 KB Output is correct
37 Correct 1316 ms 168240 KB Output is correct
38 Correct 1240 ms 166624 KB Output is correct
39 Correct 1121 ms 172552 KB Output is correct
40 Correct 1148 ms 173772 KB Output is correct
41 Correct 1223 ms 167744 KB Output is correct
42 Correct 961 ms 165632 KB Output is correct
43 Correct 1405 ms 173032 KB Output is correct
44 Correct 1317 ms 168488 KB Output is correct
45 Correct 1112 ms 172440 KB Output is correct
46 Correct 1099 ms 172180 KB Output is correct
47 Correct 995 ms 169156 KB Output is correct
48 Correct 1038 ms 168988 KB Output is correct
49 Correct 1078 ms 169144 KB Output is correct
50 Correct 961 ms 168968 KB Output is correct
51 Correct 1204 ms 172680 KB Output is correct
52 Correct 1245 ms 172640 KB Output is correct