oj.uz

Submission #938972

# Submission time Handle Problem Language Result Execution time Memory
938972 2024-03-06T02:14:22 Z LOLOLO Werewolf (IOI18_werewolf) C++17
100 / 100
 592 ms 152912 KB 
//#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100;
vector <pair <int, int>> edge[N], inc[N], dcs[N], edge2[N];
int idl[N], idr[N], l1[N], r1[N], l2[N], r2[N], pos[N], L[N], R[N], val[N * 2];
int f[N], sz[N], mx[N];

void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;  
}

int range(int l, int r) {
    return get(r) - get(l - 1);
}

vector < vector <int>> save[N];

vector <int> solve(vector <int> &p, vector <int> &q, int num) {
    int n = sz(q) - 1;
    for (int i = 1; i <= n; i++)
        pos[p[i]] = i;

    int cnt = 0;
    for (int i = 0; i < num; i++) {
        save[r2[i]].pb({l1[i], r1[i], cnt});
        L[i] = cnt;
        cnt++;
        save[l2[i] - 1].pb({l1[i], r1[i], cnt});
        R[i] = cnt;
        cnt++;
    }

    for (int i = 1; i <= n; i++) {
        int x = q[i];
        upd(pos[x], 1);

        for (auto x : save[i]) {
            val[x[2]] = range(x[0], x[1]);
        }
    }

    vector <int> ans;
    for (int i = 0; i < num; i++) {
        int v = val[R[i]] - val[L[i]];
        if (v) {
            ans.pb(1);
        } else {
            ans.pb(0);
        }
    }

    return ans;
}

struct kruskal_tree{
    int n;
    vector <int> par, arr, in, ou, mx, sz;
    vector < vector <int>> ed;

    void dfs(int u) {
        bool is = 0;
        in[u] = sz(arr);
        for (auto x : ed[u]) {
            dfs(x);
            is = 1;
        }

        if (is == 0) {
            arr.pb(u);
        }
        ou[u] = sz(arr) - 1;
    }

    void assign(int N) {
        arr.pb(0);
        n = N;
        par.assign(2 * n + 10, 0);
        in.assign(2 * n + 10, 0);
        ou.assign(2 * n + 10, 0);
        mx.assign(2 * n + 10, 0);
        sz.assign(2 * n + 10, 1);
        ed.resize(2 * n + 10);
        for (int i = 1; i <= n * 2; i++)
            mx[i] = par[i] = i;
    }

    int find(int u) {
        return par[u] == u ? u : find(par[u]);
    }

    int get(int u) {
        return mx[find(u)];
    }

    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) 
            return;

        n++;

        ed[n].pb(mx[a]);
        ed[n].pb(mx[b]);

        if (sz[a] < sz[b])
            swap(a, b);

        sz[a] += sz[b];
        par[b] = a;
        mx[a] = n;
    }
};

vector <int> check_validity(int N, vector <int> x, vector <int> y, vector <int> s, vector <int> e, vector <int> l, vector <int> r) {
    int m = sz(x);
    int n = N;

    for (int i = 0; i < m; i++) {
        x[i]++, y[i]++;
        edge[max(x[i], y[i])].pb({x[i], y[i]});
        edge2[min(x[i], y[i])].pb({x[i], y[i]});
    }

    kruskal_tree A, B;
    A.assign(n);
    B.assign(n);

    int q = sz(s);
    for (int i = 0; i < q; i++) {
        l[i]++;
        r[i]++;
        s[i]++;
        e[i]++;
        inc[r[i]].pb({e[i], i});
        dcs[l[i]].pb({s[i], i});
    }

    for (int i = 1; i <= n; i++) {
        for (auto x : edge[i]) {
            A.unite(x.f, x.s);
        }

        for (auto x : inc[i]) {
            idl[x.s] = A.get(x.f);
        }
    }

    for (int i = n; i >= 1; i--) {
        for (auto x : edge2[i]) {
            B.unite(x.f, x.s);
        }

        for (auto x : dcs[i]) {
            idr[x.s] = B.get(x.f);
        }
    }

    A.dfs(A.n);
    B.dfs(B.n);

    for (int i = 0; i < q; i++) {
        l1[i] = A.in[idl[i]];
        r1[i] = A.ou[idl[i]];
        l2[i] = B.in[idr[i]];
        r2[i] = B.ou[idr[i]];
        //cout << l1[i] << ' ' << r1[i] << ' ' << l2[i] << ' ' << r2[i] << '\n';
    }

    return solve(A.arr, B.arr, q);
}

/*int main() {
    auto v = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2}, {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
    for (auto x : v)
        cout << x << " ";

    cout << '\n';    
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34908 KB Output is correct
2 Correct 8 ms 34908 KB Output is correct
3 Correct 7 ms 34904 KB Output is correct
4 Correct 7 ms 34856 KB Output is correct
5 Correct 8 ms 34908 KB Output is correct
6 Correct 7 ms 34908 KB Output is correct
7 Correct 7 ms 34860 KB Output is correct
8 Correct 8 ms 34908 KB Output is correct
9 Correct 7 ms 34908 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34908 KB Output is correct
2 Correct 8 ms 34908 KB Output is correct
3 Correct 7 ms 34904 KB Output is correct
4 Correct 7 ms 34856 KB Output is correct
5 Correct 8 ms 34908 KB Output is correct
6 Correct 7 ms 34908 KB Output is correct
7 Correct 7 ms 34860 KB Output is correct
8 Correct 8 ms 34908 KB Output is correct
9 Correct 7 ms 34908 KB Output is correct
10 Correct 12 ms 36444 KB Output is correct
11 Correct 12 ms 36444 KB Output is correct
12 Correct 11 ms 36444 KB Output is correct
13 Correct 13 ms 36444 KB Output is correct
14 Correct 13 ms 36440 KB Output is correct
15 Correct 13 ms 34648 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 135752 KB Output is correct
2 Correct 420 ms 139316 KB Output is correct
3 Correct 431 ms 144032 KB Output is correct
4 Correct 493 ms 142080 KB Output is correct
5 Correct 465 ms 142740 KB Output is correct
6 Correct 472 ms 144456 KB Output is correct
7 Correct 443 ms 139288 KB Output is correct
8 Correct 467 ms 147416 KB Output is correct
9 Correct 401 ms 141208 KB Output is correct
10 Correct 422 ms 140320 KB Output is correct
11 Correct 414 ms 141136 KB Output is correct
12 Correct 506 ms 140956 KB Output is correct
13 Correct 457 ms 151092 KB Output is correct
14 Correct 456 ms 151060 KB Output is correct
15 Correct 449 ms 151108 KB Output is correct
16 Correct 539 ms 151116 KB Output is correct
17 Correct 460 ms 139120 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 34908 KB Output is correct
2 Correct 8 ms 34908 KB Output is correct
3 Correct 7 ms 34904 KB Output is correct
4 Correct 7 ms 34856 KB Output is correct
5 Correct 8 ms 34908 KB Output is correct
6 Correct 7 ms 34908 KB Output is correct
7 Correct 7 ms 34860 KB Output is correct
8 Correct 8 ms 34908 KB Output is correct
9 Correct 7 ms 34908 KB Output is correct
10 Correct 12 ms 36444 KB Output is correct
11 Correct 12 ms 36444 KB Output is correct
12 Correct 11 ms 36444 KB Output is correct
13 Correct 13 ms 36444 KB Output is correct
14 Correct 13 ms 36440 KB Output is correct
15 Correct 13 ms 34648 KB Output is correct
16 Correct 481 ms 135752 KB Output is correct
17 Correct 420 ms 139316 KB Output is correct
18 Correct 431 ms 144032 KB Output is correct
19 Correct 493 ms 142080 KB Output is correct
20 Correct 465 ms 142740 KB Output is correct
21 Correct 472 ms 144456 KB Output is correct
22 Correct 443 ms 139288 KB Output is correct
23 Correct 467 ms 147416 KB Output is correct
24 Correct 401 ms 141208 KB Output is correct
25 Correct 422 ms 140320 KB Output is correct
26 Correct 414 ms 141136 KB Output is correct
27 Correct 506 ms 140956 KB Output is correct
28 Correct 457 ms 151092 KB Output is correct
29 Correct 456 ms 151060 KB Output is correct
30 Correct 449 ms 151108 KB Output is correct
31 Correct 539 ms 151116 KB Output is correct
32 Correct 460 ms 139120 KB Output is correct
33 Correct 567 ms 144944 KB Output is correct
34 Correct 278 ms 97432 KB Output is correct
35 Correct 467 ms 147732 KB Output is correct
36 Correct 515 ms 144712 KB Output is correct
37 Correct 520 ms 146824 KB Output is correct
38 Correct 487 ms 145488 KB Output is correct
39 Correct 482 ms 151564 KB Output is correct
40 Correct 513 ms 151528 KB Output is correct
41 Correct 524 ms 145228 KB Output is correct
42 Correct 449 ms 140196 KB Output is correct
43 Correct 592 ms 152912 KB Output is correct
44 Correct 529 ms 147024 KB Output is correct
45 Correct 422 ms 149280 KB Output is correct
46 Correct 505 ms 149476 KB Output is correct
47 Correct 513 ms 151300 KB Output is correct
48 Correct 459 ms 151052 KB Output is correct
49 Correct 515 ms 151380 KB Output is correct
50 Correct 562 ms 151216 KB Output is correct
51 Correct 499 ms 151028 KB Output is correct
52 Correct 491 ms 150860 KB Output is correct