Submission #938972

#	Time	Username	Problem	Language	Result	Execution time	Memory
938972		LOLOLO	Werewolf (IOI18_werewolf)	C++17	100 / 100	592 ms	152912 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;
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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51