oj.uz

Submission #938856

# Submission time Handle Problem Language Result Execution time Memory
938856 2024-03-05T17:13:14 Z LOLOLO Werewolf (IOI18_werewolf) C++17
15 / 100
 386 ms 198128 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 = 1e6 + 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[N];
int cnt = 1, root[M];
 
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 6 ms 28760 KB Output is correct
2 Correct 6 ms 28764 KB Output is correct
3 Correct 6 ms 28764 KB Output is correct
4 Correct 6 ms 28780 KB Output is correct
5 Correct 6 ms 28764 KB Output is correct
6 Correct 6 ms 28760 KB Output is correct
7 Correct 6 ms 28764 KB Output is correct
8 Correct 7 ms 28764 KB Output is correct
9 Correct 6 ms 28764 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28760 KB Output is correct
2 Correct 6 ms 28764 KB Output is correct
3 Correct 6 ms 28764 KB Output is correct
4 Correct 6 ms 28780 KB Output is correct
5 Correct 6 ms 28764 KB Output is correct
6 Correct 6 ms 28760 KB Output is correct
7 Correct 6 ms 28764 KB Output is correct
8 Correct 7 ms 28764 KB Output is correct
9 Correct 6 ms 28764 KB Output is correct
10 Correct 15 ms 29788 KB Output is correct
11 Correct 12 ms 29788 KB Output is correct
12 Correct 10 ms 29788 KB Output is correct
13 Correct 20 ms 30044 KB Output is correct
14 Correct 19 ms 30044 KB Output is correct
15 Correct 19 ms 30044 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 386 ms 198128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28760 KB Output is correct
2 Correct 6 ms 28764 KB Output is correct
3 Correct 6 ms 28764 KB Output is correct
4 Correct 6 ms 28780 KB Output is correct
5 Correct 6 ms 28764 KB Output is correct
6 Correct 6 ms 28760 KB Output is correct
7 Correct 6 ms 28764 KB Output is correct
8 Correct 7 ms 28764 KB Output is correct
9 Correct 6 ms 28764 KB Output is correct
10 Correct 15 ms 29788 KB Output is correct
11 Correct 12 ms 29788 KB Output is correct
12 Correct 10 ms 29788 KB Output is correct
13 Correct 20 ms 30044 KB Output is correct
14 Correct 19 ms 30044 KB Output is correct
15 Correct 19 ms 30044 KB Output is correct
16 Runtime error 386 ms 198128 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -