oj.uz

Submission #938868

# Submission time Handle Problem Language Result Execution time Memory
938868 2024-03-05T17:25:14 Z LOLOLO Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 211796 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 142676 KB Output is correct
2 Correct 21 ms 142672 KB Output is correct
3 Correct 21 ms 142684 KB Output is correct
4 Correct 22 ms 142720 KB Output is correct
5 Correct 22 ms 142684 KB Output is correct
6 Correct 22 ms 142776 KB Output is correct
7 Correct 21 ms 142672 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 21 ms 142676 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 142676 KB Output is correct
2 Correct 21 ms 142672 KB Output is correct
3 Correct 21 ms 142684 KB Output is correct
4 Correct 22 ms 142720 KB Output is correct
5 Correct 22 ms 142684 KB Output is correct
6 Correct 22 ms 142776 KB Output is correct
7 Correct 21 ms 142672 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 21 ms 142676 KB Output is correct
10 Correct 36 ms 143704 KB Output is correct
11 Correct 30 ms 143704 KB Output is correct
12 Correct 25 ms 143696 KB Output is correct
13 Correct 35 ms 143796 KB Output is correct
14 Correct 33 ms 143864 KB Output is correct
15 Correct 34 ms 143708 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 211796 KB Output is correct
2 Execution timed out 4041 ms 198832 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 142676 KB Output is correct
2 Correct 21 ms 142672 KB Output is correct
3 Correct 21 ms 142684 KB Output is correct
4 Correct 22 ms 142720 KB Output is correct
5 Correct 22 ms 142684 KB Output is correct
6 Correct 22 ms 142776 KB Output is correct
7 Correct 21 ms 142672 KB Output is correct
8 Correct 20 ms 142684 KB Output is correct
9 Correct 21 ms 142676 KB Output is correct
10 Correct 36 ms 143704 KB Output is correct
11 Correct 30 ms 143704 KB Output is correct
12 Correct 25 ms 143696 KB Output is correct
13 Correct 35 ms 143796 KB Output is correct
14 Correct 33 ms 143864 KB Output is correct
15 Correct 34 ms 143708 KB Output is correct
16 Correct 507 ms 211796 KB Output is correct
17 Execution timed out 4041 ms 198832 KB Time limit exceeded
18 Halted 0 ms 0 KB -