Submission #75105

#	Time	Username	Problem	Language	Result	Execution time	Memory
75105		imeimi2000	Werewolf (IOI18_werewolf)	C++17	100 / 100	1058 ms	99236 KiB

werewolf

#include "werewolf.h"
#include <algorithm>

using namespace std;
typedef long long llong;

int n, m, q;
vector<int> edge[200000];

struct UF {
    int par[200000];
    UF() {
        for (int i = 0; i < 200000; ++i) par[i] = i;
    }
    int find(int x) {
        if (par[x] != x) return par[x] = find(par[x]);
        return x;
    }
} Luf, Ruf;

int Lpar[200000][20];
int Rpar[200000][20];
vector<int> Lchild[200000];
vector<int> Rchild[200000];

int Lst[200000];
int Led[200000];
int Rst[200000];
int Red[200000];
int LRd[200000];

void dfs(vector<int> child[], int st[], int ed[], int x, int &d) {
    st[x] = ++d;
    for (int i : child[x]) {
        dfs(child, st, ed, i, d);
    }
    ed[x] = d;
}

struct query {
    int i, t, x;
    query(int i, int t, int x) : i(i), t(t), x(x) {}
    bool operator<(const query &p) const {
        return t < p.t;
    }
};

int seg[200001];
void update(int i) {
    while (i <= n) {
        ++seg[i];
        i += i & -i;
    }
}

int sum(int i) {
    int ret = 0;
    while (i) {
        ret += seg[i];
        i -= i & -i;
    }
    return ret;
}

vector<int> check_validity(int N, vector<int> U, vector<int> V
                , vector<int> X, vector<int> Y, vector<int> L, vector<int> R) {
    n = N;
    m = U.size();
    q = X.size();
    for (int i = 0; i < m; ++i) {
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }
    for (int i = 0; i < n; ++i) Lpar[i][0] = 0;
    for (int i = n; i--; ) {
        for (int j : edge[i]) {
            if (j < i) continue;
            int x = Luf.find(i);
            int y = Luf.find(j);
            if (x == y) continue;
            Luf.par[y] = x;
            Lpar[y][0] = x;
            Lchild[x].push_back(y);
        }
    }
    
    for (int i = 0; i < n; ++i) Rpar[i][0] = n - 1;
    for (int i = 0; i < n; ++i) {
        for (int j : edge[i]) {
            if (i < j) continue;
            int x = Ruf.find(i);
            int y = Ruf.find(j);
            if (x == y) continue;
            Ruf.par[y] = x;
            Rpar[y][0] = x;
            Rchild[x].push_back(y);
        }
    }
    
    for (int i = 1; i < 20; ++i) {
        for (int j = 0; j < n; ++j) {
            Lpar[j][i] = Lpar[Lpar[j][i - 1]][i - 1];
            Rpar[j][i] = Rpar[Rpar[j][i - 1]][i - 1];
        }
    }
    
    int ord;
    ord = 0;
    dfs(Lchild, Lst, Led, Luf.find(0), ord);
    ord = 0;
    dfs(Rchild, Rst, Red, Ruf.find(0), ord);
    for (int i = 0; i < n; ++i) LRd[Lst[i] - 1] = Rst[i];
    
    vector<query> qs;
    for (int it = 0; it < q; ++it) {
        int x = X[it];
        int y = Y[it];
        int l = L[it];
        int r = R[it];
        for (int i = 20; i--; ) if (l <= Lpar[x][i]) x = Lpar[x][i];
        for (int i = 20; i--; ) if (Rpar[y][i] <= r) y = Rpar[y][i];
        qs.emplace_back(~it, Lst[x] - 1, y);
        qs.emplace_back(it, Led[x], y);
    }
    sort(qs.begin(), qs.end());
    vector<int> ret(q, 0);
    ord = 0;
    for (query i : qs) {
        while (ord < i.t) update(LRd[ord++]);
        int v = sum(Red[i.x]) - sum(Rst[i.x] - 1);
        if (i.i < 0) ret[~i.i] -= v;
        else ret[i.i] += v;
    }
    for (int &i : ret) i = (i > 0);
    return ret;
}

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