Submission #1233105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233105		fermat	Werewolf (IOI18_werewolf)	C++20	100 / 100	452 ms	126280 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

const int N = 2e5 + 5;

int dsu[N], hd[N], tin[N], tout[N], tiktak = 0;

vector <vector<int> > g, tmp, child[2], query;
vector <int> ans;

int get(int x) {
    return x == dsu[x] ? x : dsu[x] = get(dsu[x]);
}
void merge(int x, int y, int id) {
    x = get(x);
    y = get(y);
    if (x == y)
        return;
    dsu[y] = x;
    child[id][x].push_back(y);
}
void dfs1(int v) {
    tin[v] = ++tiktak;
    for (auto to : child[1][v]) {
        dfs1(to);
    }
    tout[v] = tiktak;
}
set <int> st[N];
void dfs0(int v) {
    for (auto to : child[0][v]) {
        dfs0(to);
        if (st[to].size() > st[v].size())
            st[v].swap(st[to]);
        for (auto x : st[to]) {
            st[v].insert(x);
        }
    }
    st[v].insert(tin[v]);
    for (auto to : query[v]) {
        auto it = st[v].lower_bound(tin[hd[to]]);
        if (it != st[v].end() && *it <= tout[hd[to]]) {
            ans[to] = 1;
        }
    }
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    g.resize(N);
    child[0].resize(N);
    child[1].resize(N);
    query.resize(N);
    ans.resize(Q, 0);
    for (int i = 0; i < X.size(); i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    iota(dsu, dsu + N, 0);
    tmp.clear();
    tmp.resize(N);
    for (int i = 0; i < Q; i++) {
        tmp[R[i]].push_back(i);
    }   
    for (int i = 0; i < N; i++) {
        for (auto j : g[i]) {
            if (i > j)
                merge(i, j, 1);
        }
        for (auto j : tmp[i]) {
            hd[j] = get(E[j]);
        }
    }
    iota(dsu, dsu + N, 0);
    tmp.clear();
    tmp.resize(N);
    for (int i = 0; i < Q; i++) {
        tmp[L[i]].push_back(i);
    }
    for (int i = N - 1; i >= 0; i--) {
        for (auto j : g[i]) {
            if (i < j)
                merge(i, j, 0);
        }
        for (auto j : tmp[i]) {
            query[get(S[j])].push_back(j);
        }
    }
    dfs1(N - 1);
    dfs0(0);
    return ans;
}

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