Submission #414102

#	Time	Username	Problem	Language	Result	Execution time	Memory
414102		ja_kingy	Werewolf (IOI18_werewolf)	C++17	100 / 100	1486 ms	178068 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

//10:20

const int mxN = 2e5;
template <class T>
struct KRT {
    int ncnt, dsu[2*mxN], val[2*mxN], anc[2*mxN][19];
    vector<int> g[2*mxN];
    T cmp;
    int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
    KRT (int n, vector<int> &u, vector<int> &v) : ncnt(n) {
        iota(begin(dsu), end(dsu), 0);
        vector<int> order(u.size());
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int a, int b) {return cmp(max(u[a], v[a], cmp), max(u[b], v[b], cmp));});
        for (int e: order) {
            int a = f(u[e]), b = f(v[e]);
            if (a != b) {
                anc[a][0] = anc[b][0] = dsu[b] = dsu[a] = ncnt;
                val[ncnt] = max(u[e], v[e], cmp);
                g[ncnt].push_back(a);
                g[ncnt].push_back(b);
                ncnt++;
            }            
        }
        anc[ncnt-1][0] = ncnt-1;
        for (int i = 1; i < 19; ++i) for (int j = 0; j < ncnt; ++j) anc[j][i] = ncnt-1;
        for (int i = 1; i < 19; ++i) {
            for (int j = 0; j < ncnt; ++j) {
                anc[j][i] = anc[anc[j][i-1]][i-1];
            }
        }
    }
    int thresh(int x, int v) {
        for (int i = 19; i--;) {
            if (!cmp(v,val[anc[x][i]])) x = anc[x][i]; 
        }
        return x;
    }
};

int tcnt, st[2*mxN], en[2*mxN];
void dfs1(int u, KRT<less<int>> &k) {
    st[u] = tcnt++;
    for (int v: k.g[u]) dfs1(v, k);
    en[u] = tcnt;
}

struct qry {int l, r, id;};
vector<qry> qrys[2*mxN];
vector<int> ans;
set<int> sts[2*mxN];
void dfs2(int u, KRT<greater<int>> &k) {
    for (int v: k.g[u]) {
        dfs2(v, k);
        if (sts[u].size() < sts[v].size()) swap(sts[u], sts[v]);
        sts[u].merge(sts[v]);
    }
    for (qry q: qrys[u]) {
        auto it = sts[u].lower_bound(q.l);
        ans[q.id] = it != sts[u].end() && *it < q.r;
    }
}

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 Q = S.size();
    ans.resize(Q);
    KRT<less<int>> wolf(N,X,Y);
    KRT<greater<int>> human(N,X,Y);
    dfs1(wolf.ncnt-1, wolf);
    for (int i = 0; i < N; ++i) sts[i].insert(st[i]);
    for (int i = 0; i < Q; ++i) {
        int x = wolf.thresh(E[i], R[i]);
        qrys[human.thresh(S[i], L[i])].push_back({st[x], en[x], i});
    }
    dfs2(human.ncnt-1, human);
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51