제출 #434478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434478		dxz05	늑대인간 (IOI18_werewolf)	C++14	0 / 100	1487 ms	90248 KiB

werewolf

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

using namespace std;

const int MAXN = 4e5 + 3e2;

vector<int> g[MAXN];

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

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

}

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

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 = 0; j < n; j++){
            if (i == 0){
                t[j][i] = MP(vec[j], vec[j]);
            } else {
                if (j + (1 << i) - 1 <= n) 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];
    return combine(t[l][x], t[r - (1 << x) + 1][x]);
}

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

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

    l = X, r = N - 1;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(X, m);
        if (f.first >= L && f.second <= R){
            rg = l;
            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];

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]);
    }

    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));
    }

    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 + 1) - get(l);

            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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51