제출 #434460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434460		dxz05	늑대인간 (IOI18_werewolf)	C++14	0 / 100	4053 ms	58056 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[4 * MAXN];

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

void build(int v, int tl, int tr){
    if (tl == tr){
        t[v].first = t[v].second = vec[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);

    t[v] = combine(t[v + v], t[v + v + 1]);
}

PII get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return t[v];
    if (tl > r || tr < l) return MP(1e9, -1e9);
    int tm = (tl + tr) >> 1;
    return combine(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

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

    int l = 0, r = X;
    while (l <= r){
        int m = (l + r) >> 1;
        PII f = get(1, 0, N - 1, 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(1, 0, N - 1, 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(1, 0, N - 1);


    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 l = max(fs.first, fe.first), r = min(fs.second, fe.second);
        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++){
        smaller[i] = get(tin[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;
            int res = get(r);
            if (l) res -= 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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51