Submission #477652

#	Time	Username	Problem	Language	Result	Execution time	Memory
477652		SirCovidThe19th	Werewolf (IOI18_werewolf)	C++17	15 / 100	1463 ms	524292 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 ty){
    a = get(a); b = get(b); if (a == b) return;
    if (!ty) dsuAdj[id].push_back(a), dsuAdj[id].push_back(b);
    else{
        nodes[id].insert(nodes[a].begin(), nodes[a].end());
        nodes[id].insert(nodes[b].begin(), nodes[b].end()); 
    }
    par[a] = par[b] = id++;
}
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], st1(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, 0); 
        for (int qry : QL[i]) st1[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); id = n;
    for (int i = 0; i < n; i++){
        for (int x : adj[i]) if (x < i) merge(i, x, 1);
        for (int qry : QR[i]){
            int st2 = get(E[qry]);
            auto it = nodes[st2].lower_bound(tin[st1[qry]]);
            if (it != nodes[st2].end() and *it <= tout[st1[qry]]) ans[qry] = 1;
        }
    }
    return ans;
}

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