Submission #938860

#	Time	Username	Problem	Language	Result	Execution time	Memory
938860		LOLOLO	Werewolf (IOI18_werewolf)	C++17	15 / 100	4037 ms	213328 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51