oj.uz

Submission #938860

# Submission time Handle Problem Language Result Execution time Memory
938860 2024-03-05T17:15:57 Z LOLOLO Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 213328 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, M = 1e7 + 10;
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];

struct node{
    int s = 0;
    int lson, rson;
 
    node() {};
};
 
node seg[M];
int cnt = 1, root[N];
 
void build(int id, int l, int r) {
    if (l == r) {
        return;
    }
 
    int m = (l + r) / 2;
    seg[id].lson = cnt++;
    seg[id].rson = cnt++;
 
    build(seg[id].lson, l, m);
    build(seg[id].rson, m + 1, r);
}
 
void upd(int pid, int id, int l, int r, int v) {
    if (l > v || r < v)
        return;
 
    if (l == r) {
        return;
    }
 
    int m = (l + r) / 2;
    if (v <= m) {
        seg[id].rson = seg[pid].rson;
        seg[id].lson = cnt;
        seg[cnt].s = seg[seg[pid].lson].s + 1;
        cnt++;
        upd(seg[pid].lson, seg[id].lson, l, m, v);
    } else {
        seg[id].lson = seg[pid].lson;
        seg[id].rson = cnt;
        seg[cnt].s = seg[seg[pid].rson].s + 1;
        cnt++;
        upd(seg[pid].rson, seg[id].rson, m + 1, r, v);
    }
}
 
ll get(int id, int l, int r, int u, int v) {
    if (l > v || r < u)
        return 0;
 
    if (l >= u && r <= v) {
        return seg[id].s;
    }
 
    int m = (l + r) / 2;
    return get(seg[id].lson, l, m, u, v) + get(seg[id].rson, m + 1, r, u, v);
}

int pos[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;

    build(0, 1, n);
    root[0] = 0;

    for (int i = 1; i <= n; i++) {
        //cout << q[i] << " ";
        int x = q[i];
        cnt++;
        root[i] = cnt - 1;
        seg[root[i]].s = seg[root[i - 1]].s + 1;
        upd(root[i - 1], root[i], 1, n, pos[x]);
    }

    //cout << '\n';

    vector <int> save;
    for (int i = 0; i < num; i++) {
        int v = get(root[r2[i]], 1, n, l1[i], r1[i]) - get(root[l2[i] - 1], 1, n, l1[i], r1[i]);
        if (v) {
            save.pb(1);
        } else {
            save.pb(0);
        }
    }

    return save;
}

struct kruskal_tree{
    int n;
    vector <int> par, arr, in, ou;
    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);
        ed.resize(2 * n + 10);
        for (int i = 1; i <= n * 2; i++)
            par[i] = i;
    }

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

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

        n++;
        par[a] = par[b] = par[n] = n;
        ed[n].pb(a);
        ed[n].pb(b);
    }
};

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.find(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.find(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);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 142672 KB Output is correct
2 Correct 22 ms 142684 KB Output is correct
3 Correct 21 ms 142676 KB Output is correct
4 Correct 20 ms 142684 KB Output is correct
5 Correct 21 ms 142684 KB Output is correct
6 Correct 21 ms 142680 KB Output is correct
7 Correct 20 ms 142780 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 23 ms 142936 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 142672 KB Output is correct
2 Correct 22 ms 142684 KB Output is correct
3 Correct 21 ms 142676 KB Output is correct
4 Correct 20 ms 142684 KB Output is correct
5 Correct 21 ms 142684 KB Output is correct
6 Correct 21 ms 142680 KB Output is correct
7 Correct 20 ms 142780 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 23 ms 142936 KB Output is correct
10 Correct 30 ms 143892 KB Output is correct
11 Correct 31 ms 143708 KB Output is correct
12 Correct 25 ms 143708 KB Output is correct
13 Correct 35 ms 143964 KB Output is correct
14 Correct 35 ms 143872 KB Output is correct
15 Correct 34 ms 143880 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 213328 KB Output is correct
2 Execution timed out 4037 ms 207212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 142672 KB Output is correct
2 Correct 22 ms 142684 KB Output is correct
3 Correct 21 ms 142676 KB Output is correct
4 Correct 20 ms 142684 KB Output is correct
5 Correct 21 ms 142684 KB Output is correct
6 Correct 21 ms 142680 KB Output is correct
7 Correct 20 ms 142780 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 23 ms 142936 KB Output is correct
10 Correct 30 ms 143892 KB Output is correct
11 Correct 31 ms 143708 KB Output is correct
12 Correct 25 ms 143708 KB Output is correct
13 Correct 35 ms 143964 KB Output is correct
14 Correct 35 ms 143872 KB Output is correct
15 Correct 34 ms 143880 KB Output is correct
16 Correct 553 ms 213328 KB Output is correct
17 Execution timed out 4037 ms 207212 KB Time limit exceeded
18 Halted 0 ms 0 KB -