Submission #439898

#	Time	Username	Problem	Language	Result	Execution time	Memory
439898		dxz05	Werewolf (IOI18_werewolf)	C++14	49 / 100	1883 ms	98512 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4e5 + 3e2;

#define MP make_pair
#define PII pair<int, int>

vector<int> g[MAXN];

bool used[MAXN];
int tin[MAXN];
vector<int> vec = {0};
void dfs(int v){
    used[v] = true;
    tin[v] = vec.size();
    vec.push_back(v);

    for (int u : g[v]){
        if (!used[u]){
            dfs(u);
        }
    }

}


PII t[MAXN][20];
int Log[MAXN];

PII combine(PII lf, PII rg){
    return MP(min(lf.first, rg.first), max(lf.second, rg.second));
}

void build(int n){
    Log[1] = 0;
    for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
    for (int i = 0; i < 20; i++){
        for (int j = 1; j <= n; j++){
            if (i == 0){
                t[j][i] = MP(vec[j], vec[j]);
            } else {
                if (j + (1 << (i - 1)) < MAXN) t[j][i] = combine(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
}

PII get(int l, int r){
    if (l > r) return MP(1e9, -1e9);
    if (l == r) return t[l][0];
    int x = Log[r - l + 1];
    PII res = combine(t[l][x], t[r - (1 << x) + 1][x]);

    return res;
}

PII get_positions(int X, int N, int L, int R){
    X = tin[X];
    int lf = X, rg = X;

    int l = 1, r = X;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(m, X);
        if (f.first >= L && f.second <= R){
            lf = m;
            r = m - 1;
        } else l = m + 1;
    }

    l = X, r = N;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(X, m);
        if (f.first >= L && f.second <= R){
            rg = m;
            l = m + 1;
        } else r = m - 1;
    }

    return MP(lf, rg);
}

int smaller[MAXN];

int fw[MAXN];
void add(int x, int y){
    while (x < MAXN){
        fw[x] += y;
        x += (-x & x);
    }
}

int get(int x){
    int ret = 0;
    while (x > 0){
        ret += fw[x];
        x -= (-x & x);
    }
    return ret;
}

vector<pair<PII, PII>> queries[MAXN];


void dfs2(int v, int l, int r, vector<bool> &used){
    used[v] = true;

    for (int u : g[v]){
        if (!used[u] && l <= u && u <= r){
            dfs2(u, l, r, used);
        }
    }
}

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(), M = X.size();
    vector<int> A(Q, 0);

    for (int i = 0; i < M; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }

    if (N <= 3000 && M <= 6000 && Q <= 3000){
        for (int i = 0; i < Q; i++){
            vector<bool> used1(N, false), used2(N, false);
            dfs2(S[i], L[i], N - 1, used1);
            dfs2(E[i], 0, R[i], used2);

            for (int j = L[i]; j <= R[i]; j++){
                if (used1[j] && used2[j]) A[i] = 1;
            }

        }

        return A;
    }

    for (int i = 0; i < N; i++){
        if (g[i].size() == 1){
            dfs(i);
            break;
        }
    }

    build(N);

    for (int i = 0; i < Q; i++){
        PII fs = get_positions(S[i], N, L[i], N - 1), fe = get_positions(E[i], N, 0, R[i]);
        int l1 = fs.first, r1 = fs.second, l2 = fe.first, r2 = fe.second;

        //cout << "\t" << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;

        int l = max(l1, l2), r = min(r1, r2);
        if (L[i]) queries[L[i] - 1].emplace_back(MP(i, 0), MP(l, r));
        queries[R[i]].emplace_back(MP(i, 1), MP(l, r));

    }

    //return A;

    for (int i = 0; i < N; i++){
        add(tin[i], 1);

        for (auto qu : queries[i]){
            int ind = qu.first.first, ty = qu.first.second, l = qu.second.first, r = qu.second.second;
           // cout << i << ' ' << l << ' ' << r << endl;
            int res = get(r) - get(l - 1);

            if (ty == 0) A[ind] -= res; else
                A[ind] += res;

        }

    }

    for (int i = 0; i < Q; i++) A[i] = A[i] > 0;


    return A;
}

/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4


6 5 1
2 0
0 1
3 5
1 3
5 4
1 4 0 4

*/

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