제출 #1044918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044918		VMaksimoski008	늑대인간 (IOI18_werewolf)	C++17	100 / 100	559 ms	226852 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 6e5 + 5;

struct BIT {
    int n;
    vector<int> tree;

    void config(int _n) {
        n = _n + 10;
        tree.resize(_n+60);
    }

    void update(int p, int v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p>0; p-=p&-p) ans += tree[p];
        return ans;
    }

    int query(int l, int r) { return query(r) - query(l-1); }
};

int par[2][maxn], n, d[2][maxn], mn[maxn], mx[maxn], out[2][maxn], up[2][maxn][21], in[2][maxn], timer[2];
vector<int> graph[2][maxn], euler[2];
vector<int> by_x[maxn+5];

int find(int u, int t) {
    if(par[t][u] == u) return u;
    return par[t][u] = find(par[t][u], t);
}

void uni(int a, int b, int t) {
    a = find(a, t); b = find(b, t);
    if(a == b) return ;
    n++;
    par[t][n] = par[t][a] = par[t][b] = n;
    graph[t][n].push_back(a);
    graph[t][n].push_back(b);
}

void dfs(int u, int t) {
    if(graph[t][u].empty()) {
        if(t == 0) mn[u] = u;
        else mx[u] = u;
    }

    in[t][u] = timer[t]++; euler[t].push_back(u);
    for(int i=1; i<21; i++) up[t][u][i] = up[t][up[t][u][i-1]][i-1];

    for(int &v : graph[t][u]) {
        d[t][v] = d[t][u] + 1;
        up[t][v][0] = u;
        dfs(v, t);
        if(t == 0) mn[u] = min(mn[u], mn[v]);
        else mx[u] = max(mx[u], mx[v]);
    }

    out[t][u] = timer[t] - 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) {
    int Q = S.size(), M = X.size();
    vector<int> ans(Q);

    for(int i=1; i<=N+M; i++) par[0][i] = par[1][i] = i, mn[i] = 1e9;

    vector<int> edges[N+1];
    for(int i=0; i<M; i++) {
        edges[X[i]+1].push_back(Y[i]+1);
        edges[Y[i]+1].push_back(X[i]+1);
    }

    n = N;
    for(int i=N; i>=1; i--)
        for(int &j : edges[i]) if(i < j) uni(i, j, 0);
    n = N;
    for(int i=1; i<=N; i++)
        for(int &j : edges[i]) if(i > j) uni(i, j, 1);

    dfs(n, 0); dfs(n, 1);

    vector<array<int, 4> > qus;    
    for(int i=1; i<=N; i++) by_x[in[0][i]].push_back(in[1][i]);
    for(int i=0; i<Q; i++) {
        S[i]++; E[i]++; L[i]++; R[i]++;
        if(S[i] < L[i] || E[i] > R[i]) continue;
        int p1 = S[i], p2 = E[i];

        for(int j=20; j>=0; j--) {
            if(up[0][p1][j] > 0 && mn[up[0][p1][j]] >= L[i]) p1 = up[0][p1][j];
            if(up[1][p2][j] > 0 && mx[up[1][p2][j]] <= R[i]) p2 = up[1][p2][j];
        }

        qus.push_back({ in[0][p1], out[0][p1], in[1][p2], out[1][p2] });
    }

    vector<int> on[n+1], off[n+1], add[n+1];
    for(int i=0; i<Q; i++) {
        on[qus[i][1]].push_back(i);
        if(qus[i][0]) off[qus[i][0]-1].push_back(i);
    }

    BIT bit; bit.config(n+1);
    for(int i=0; i<=n; i++) {
        for(int &p : by_x[i]) bit.update(p, 1);
        for(int &id : off[i]) ans[id] -= bit.query(qus[id][2], qus[id][3]);
        for(int &id : on[i]) ans[id] += bit.query(qus[id][2], qus[id][3]);
    }

    for(int i=0; i<Q; i++) {
        if(ans[i] >= 1) ans[i] = 1;
        else ans[i] = 0;
    }
    return ans;
}

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