Submission #78781

#	Time	Username	Problem	Language	Result	Execution time	Memory
78781		wleung_bvg	Werewolf (IOI18_werewolf)	C++14	100 / 100	1392 ms	297016 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, MAXLGN = 20;

int UF[2][MAXN], PAR[2][MAXLGN][MAXN], PRE[2][MAXN], POST[2][MAXN], VERT[2][MAXN], BIT[MAXN], ANS[MAXQ], cur;
vector<int> ADJ[MAXN], TR[2][MAXN];
vector<pii> ADD[MAXN], SUB[MAXN];

int find(int i, int v) {
    return UF[i][v] < 0 ? v : UF[i][v] = find(i, UF[i][v]);
}

void join(int i, int v, int w) {
    v = find(i, v);
    w = find(i, w);
    if (v == w) return;
    UF[i][w] = v;
    TR[i][v].pb(w);
    PAR[i][0][w] = v;
}

void dfs(int i, int v) {
    VERT[i][PRE[i][v] = ++cur] = v;
    FORE(w, TR[i][v]) dfs(i, w);
    POST[i][v] = cur;
}

void update(int i, int v) {
    for (; i < MAXN; i += i & -i) BIT[i] += v;
}

int rsq(int i) {
    int ret = 0;
    for (; i > 0; i -= i & -i) ret += BIT[i];
    return ret;
}

int rsq(int a, int b) {
    return rsq(b) - rsq(a - 1);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    FOR(i, sz(X)) {
        ADJ[X[i]].pb(Y[i]);
        ADJ[Y[i]].pb(X[i]);
    }
    FOR(i, 2) fill(UF[i], UF[i] + MAXN, -1);
    PAR[0][0][0] = 0;
    REV(i, N - 1) FORE(j, ADJ[i]) if (i < j) join(0, i, j);
    PAR[1][0][N - 1] = N - 1;
    FOR(i, N) FORE(j, ADJ[i]) if (i > j) join(1, i, j);
    cur = 0;
    dfs(0, 0);
    cur = 0;
    dfs(1, N - 1);
    FOR(i, 2) For(j, 1, MAXLGN) FOR(k, N) PAR[i][j][k] = PAR[i][j - 1][PAR[i][j - 1][k]];
    FOR(i, sz(S)) {
        int s = S[i], e = E[i];
        REV(j, MAXLGN - 1) {
            if (PAR[0][j][s] >= L[i]) s = PAR[0][j][s];
            if (PAR[1][j][e] <= R[i]) e = PAR[1][j][e];
        }
        ADD[POST[1][e]].eb(s, i);
        SUB[PRE[1][e] - 1].eb(s, i);
    }
    fill(BIT, BIT + MAXN, 0);
    fill(ANS, ANS + MAXQ, 0);
    For(i, 1, N + 1) {
        update(PRE[0][VERT[1][i]], 1);
        FORE(q, ADD[i]) ANS[q.s] += rsq(PRE[0][q.f], POST[0][q.f]);
        FORE(q, SUB[i]) ANS[q.s] -= rsq(PRE[0][q.f], POST[0][q.f]); 
    }
    vector<int> ret;
    FOR(i, sz(S)) ret.pb(ANS[i] > 0);
    return ret;
}

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