Submission #477659

#	Time	Username	Problem	Language	Result	Execution time	Memory
477659		SirCovidThe19th	Werewolf (IOI18_werewolf)	C++17	100 / 100	872 ms	157344 KiB

werewolf

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

#define vi vector<int>

const int mx = 6e5 + 5;

int par[mx], tin[mx], tout[mx], ti, id; vector<int> dsuAdj[mx]; set<int> nodes[mx];

int get(int i){ 
    return i == par[i] ? i : par[i] = get(par[i]); 
}
void merge(int a, int b, bool build){
    a = get(a); b = get(b); if (a == b) return;
    if (build){
        dsuAdj[id].push_back(a); dsuAdj[id].push_back(b);
        par[a] = par[b] = id++;
    }
    else{
        if (nodes[a].size() > nodes[b].size()) swap(a, b); 
        par[a] = b;
        nodes[b].insert(nodes[a].begin(), nodes[a].end());
    }
}
void dfs(int i){
    tin[i] = ti++;
    for (int x : dsuAdj[i]) dfs(x);
    tout[i] = ti - 1;
}

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){
    int m = X.size(), q = L.size();  
    
    vi adj[n], QL[n], QR[n], st(q), ans(q);
    
    for (int i = 0; i < m; i++) adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);
    for (int i = 0; i < q; i++) QL[L[i]].push_back(i), QR[R[i]].push_back(i);

    iota(par, par + n * 2, 0); id = n;
    for (int i = n - 1; ~i; i--){
        for (int x : adj[i]) if (x > i) merge(i, x, 1); 
        for (int qry : QL[i]) st[qry] = get(S[qry]);
    }
    
    dfs(id - 1); 
    for (int i = 0; i < n; i++) nodes[i].insert(tin[i]);
    
    iota(par, par + n * 2, 0);
    for (int i = 0; i < n; i++){
        for (int x : adj[i]) if (x < i) merge(i, x, 0);
        for (int qry : QR[i]){
            int cmp = get(E[qry]);
            auto it = nodes[cmp].lower_bound(tin[st[qry]]);
            if (it != nodes[cmp].end() and *it <= tout[st[qry]]) ans[qry] = 1;
        }
    }
    return ans;
}

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