제출 #1219348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219348		vanea	늑대인간 (IOI18_werewolf)	C++20	100 / 100	619 ms	97920 KiB

werewolf

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

const int mxN = 5e5+10;

int p[mxN], tin[mxN], tout[mxN], cnt = -1, tin1[mxN], tout1[mxN];
bool added[mxN];
vector<int> adj[mxN], adj1[mxN];

int st[mxN*4];

void upd(int node, int l, int r, int k) {
    if(l == r && l == k) {
        st[node] = 1;
        return ;
    }
    if(l > k || r < k) return ;
    int mid = (l+r)/2;
    upd(node*2, l, mid, k);
    upd(node*2+1, mid+1, r, k);
    st[node] = st[node*2] + st[node*2+1];
}

int qry(int node, int l, int r, int l1, int r1) {
    if(l1 <= l && r <= r1) return st[node];
    if(l1 > r || r1 < l) return 0;
    int mid = (l+r)/2;
    return qry(node*2, l, mid, l1, r1) + qry(node*2+1, mid+1, r, l1, r1);
}

int get(int x) {
    return p[x] == x ? x : p[x] = get(p[x]);
}

void uni(int a, int b) {
    p[a] = p[b] = b;
    adj1[b].push_back(a);
}

void dfs(int node, int p) {
    tin[node] = ++cnt;
    for(auto it : adj1[node]) {
        if(it == p) continue;
        dfs(it, node);
    }
    tout[node] = cnt;
}

void dfs1(int node, int p) {
    tin1[node] = ++cnt;
    for(auto it : adj1[node]) {
        if(it == p) continue;
        dfs1(it, node);
    }
    tout1[node] = cnt;
}

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 M = X.size(); int n = N;
    iota(p, p+n+1, 0);
    for(int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    int q = L.size();
    vector<vector<array<int, 2>>> queries_l(n+1);
    vector<vector<array<int, 2>>> queries_r(n+1);
    vector<int> root(q+1);
    vector<array<array<int, 2>, 2>> ranges(q+1);
    for(int i = 0; i < q; i++) {
        queries_r[R[i]].push_back({E[i], i});
        queries_l[L[i]].push_back({S[i], i});
    }
    for(int i = 0; i < n; i++) {
        added[i] = true;
        for(auto it : adj[i]) {
            if(added[it]) {
                int par = get(it);
                if(par == i) continue;
                uni(par, i);
            }
        }
        for(auto [it, idx] : queries_r[i]) {
            int par = get(it);
            root[idx] = par;
        }
    }
    dfs(n-1, n-1);
    for(int i = 0; i < q; i++) {
        ranges[i][0] = {tin[root[i]], tout[root[i]]};
    }
    memset(added, false, sizeof added); iota(p, p+n+1, 0);
    for(int i = 0; i < n; i++) adj1[i].clear();
    for(int i = n-1; i >= 0; i--) {
        added[i] = true;
        for(auto it : adj[i]) {
            if(added[it]) {
                int par = get(it);
                if(par == i) continue;
                uni(par, i);
            }
        }
        for(auto [it, idx] : queries_l[i]) {
            int par = get(it);
            root[idx] = par;
        }
    }
    cnt = -1;
    dfs1(0, 0);
    vector<int> ans(q, 0);
    vector<int> past(q+1, 0);
    vector<vector<array<int, 4>>> queries(n);
    for(int i = 0; i < q; i++) {
        ranges[i][1] = {tin1[root[i]], tout1[root[i]]};
        if(ranges[i][0][0] - 1 != -1)   queries[ranges[i][0][0]-1].push_back({-1, tin1[root[i]], tout1[root[i]], i});
        queries[ranges[i][0][1]].push_back({1, tin1[root[i]], tout1[root[i]], i});
    }
    vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return tin[a] < tin[b];
    });
    for(int i = 0; i < n; i++) {
        upd(1, 0, n, tin1[ord[i]]);
        for(auto [flag, l, r, idx] : queries[i]) {
            if(flag == 1) {
                int now = qry(1, 0, n, l, r);
                if(now > past[idx]) ans[idx] = 1;
            }
            else {
                int now = qry(1, 0, n, l, r);
                past[idx] = now;
            }
        }
    }
    return ans;
}

/*int main()
{
    vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
    {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
    for(auto it : ans) {
        cout << it << ' ';
    }
    return 0;
}*/

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