Submission #1226979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226979		Hamed_Ghaffari	Werewolf (IOI18_werewolf)	C++20	100 / 100	528 ms	100476 KiB

werewolf

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

const int MXN = 2e5+5;

vector<int> g[MXN], ch[2][MXN], Q[MXN], tmp[MXN];
int dsu[MXN], wh[MXN];

int find(int v) { return v==dsu[v] ? v : dsu[v]=find(dsu[v]); }
void merge(int u, int v, int id) {
    u = find(u), v = find(v);
    if(u==v) return;
    ch[id][dsu[v] = u].push_back(v);
}

int stt[MXN], fnt[MXN], timer;
vector<int> ans;

void dfs1(int v) {
    stt[v] = timer++;
    for(int u : ch[1][v])
        dfs1(u);
    fnt[v] = timer;
}

set<int> st[MXN];
void dfs0(int v) {
    for(int u : ch[0][v]) {
        dfs0(u);
        if(st[v].size()<st[u].size()) st[v].swap(st[u]);
        for(int x : st[u]) st[v].insert(x);
        st[u].clear();
    }
    st[v].insert(stt[v]);
    for(int i : Q[v]) {
        auto it = st[v].lower_bound(stt[wh[i]]);
        if(it!=st[v].end() && (*it)<fnt[wh[i]]) ans[i] = 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) {
    for(int i=0; i<X.size(); i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<L.size(); i++) tmp[L[i]].push_back(i);
    iota(dsu, dsu+N, 0);
    for(int i=N-1; i>=0; i--) {
        for(int j : g[i])
            if(j>i)
                merge(i, j, 0);
        for(int j : tmp[i])
            Q[find(S[j])].push_back(j);
    }
    for(int i=0; i<N; i++) tmp[i].clear();
    for(int i=0; i<R.size(); i++) tmp[R[i]].push_back(i);
    iota(dsu, dsu+N, 0);
    for(int i=0; i<N; i++) {
        for(int j : g[i])
            if(j<i)
                merge(i, j, 1);
        for(int j : tmp[i])
            wh[j] = find(E[j]);
    }
    dfs1(N-1);
    ans = vector<int>(L.size(), 0);
    dfs0(0);
    return ans;
}

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