제출 #1219318

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

werewolf

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

const int mxN = 2e5+10;

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

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 uni1(int a, int b) {
    if(s[b].size() < s[a].size()) swap(s[a], s[b]);
    for(auto it : s[a]) s[b].insert(it);
    p[a] = p[b] = b;
}

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]);
    }
    vector<vector<array<int, 3>>> queries(n+1);
    vector<vector<array<int, 2>>> queries_r(n+1);
    int q = L.size();
    for(int i = 0; i < q; i++) {
        queries[L[i]].push_back({R[i], S[i], i});
        queries_r[R[i]].push_back({E[i], i});
    }
    for(int i = 0; i < n; i++) {
        added[i] = true;
        for(auto it : adj[i]) {
            if(added[it]) {
                int par = get(it);
                uni(par, i);
            }
        }
    }
    vector<int> ans(q);
    dfs(n-1, n-1);
    for(int i = 0; i < n; i++) {
        for(auto [it, idx] : queries_r[i]) {
            if(tin[i] <= tin[it] && tin[it] <= tout[i]) ans[idx] = 1;
        }
    }
    iota(p, p+n+1, 0); memset(added, false, sizeof added);
    for(int i = 0; i < n; i++) s[i].insert(tin[i]);
    for(int i = n-1; i >= 0; i--) {
        added[i] = true;
        for(auto it : adj[i]) {
            if(added[it]) {
                int par = get(it);
                uni1(par, i);
            }
        }
        for(auto [it, st, idx] : queries[i]) {
            if(s[i].count(tin[st]) == 0) ans[idx] = 0;
            auto it1 = s[i].lower_bound(tin[it]);
            if(it1 != s[i].end() && *it1 <= tout[it]) ans[idx] = ans[idx] & 1;
            else ans[idx] = 0;
        }
    }
    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51