Submission #81140

#	Time	Username	Problem	Language	Result	Execution time	Memory
81140		cki86201	Werewolf (IOI18_werewolf)	C++11	100 / 100	1047 ms	425572 KiB

werewolf

#include "werewolf.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

struct tree {
    vector <int> F[200020];
    int lv[200020], rv[200020], cs = 0;
    int up[200020][18];
    void addE(int x, int y) {   // x <- y
        F[x].pb(y);
    }
    void dfs(int x) {
        lv[x] = ++cs;
        for(int e : F[x]) {
            up[e][0] = x;
            for(int i=1;i<18;i++) {
                up[e][i] = up[ up[e][i-1] ][i-1];
            }
            dfs(e);
        }
        rv[x] = cs;
    }
    pii get_seg_g(int x, int l) {
        for(int i=17;i>=0;i--) {
            if(up[x][i] && up[x][i] >= l) x = up[x][i];
        }
        return pii(lv[x], rv[x]);
    }
    pii get_seg_l(int x, int r) {
        for(int i=17;i>=0;i--) {
            if(up[x][i] && up[x][i] <= r) x = up[x][i];
        }
        return pii(lv[x], rv[x]);
    }
} T[2];

int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
int val[200020];
vector <int> EE[200010];
int N;

vector <t3> pquery[200020];
int TT[200020];
int cnt[200020];

void pre_query(int idx, int S, int E, int L, int R) {
    pii p1 = T[0].get_seg_l(E, R);
    pii p2 = T[1].get_seg_g(S, L);
    pquery[p1.Se].pb(t3(p2.Se, idx, 1));
    pquery[p1.Se].pb(t3(p2.Fi-1, idx, -1));
    pquery[p1.Fi-1].pb(t3(p2.Se, idx, -1));
    pquery[p1.Fi-1].pb(t3(p2.Fi-1, idx, 1));
}

std::vector<int> check_validity(int nn, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    N = nn;
    int M = szz(X);
    for(int i=0;i<M;i++) {
        int x = X[i] + 1, y = Y[i] + 1;
        EE[x].pb(y);
        EE[y].pb(x);
    }
    for(int i=1;i<=N;i++) pp[i] = i;
    for(int i=1;i<=N;i++) {
        for(int e : EE[i]) if(e < i) {
            int x = Find(i), y = Find(e);
            if(x == y) continue;
            pp[y] = x;
            T[0].addE(x, y);
        }
    }
    for(int i=1;i<=N;i++) pp[i] = i;
    for(int i=N;i;i--) {
        for(int e : EE[i]) if(e > i) {
            int x = Find(i), y = Find(e);
            if(x == y) continue;
            pp[y] = x;
            T[1].addE(x, y);
        }
    }
    T[0].dfs(N); T[1].dfs(1);
    for(int i=1;i<=N;i++) {
        val[T[0].lv[i]] = T[1].lv[i];
    }
    int Q = szz(S);
    rep(i, Q) {
        ++S[i]; ++E[i]; ++L[i]; ++R[i];
        pre_query(i, S[i], E[i], L[i], R[i]);
    }
    for(int i=1;i<=N;i++) {
        int x = val[i];
        for(int j=x;j<200020;j+=(j&-j)) TT[j]++;
        for(t3 e : pquery[i]) {
            int y, idx, cc;
            tie(y, idx, cc) = e;
            int s = 0;
            for(int j=y;j;j-=(j&-j)) s += TT[j];
            cnt[idx] += cc * s;
        }
    }
    vector <int> A(Q);
    rep(i, Q) {
        A[i] = cnt[i] > 0 ? 1 : 0;
    }
    return A;
}

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