Submission #477644

#	Time	Username	Problem	Language	Result	Execution time	Memory
477644		SirCovidThe19th	Werewolf (IOI18_werewolf)	C++17	100 / 100	3878 ms	352436 KiB

werewolf

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

#define vi vector<int>

const int mx = 6e5 + 5;

struct dsuTree{
    int par[mx], tin[mx], tout[mx], ti, id; vector<int> adj[mx];
    dsuTree(int n){ 
        iota(par, par + n * 2, 0); id = n; 
    }
    int get(int i){ 
        return i == par[i] ? i : par[i] = get(par[i]); 
    }
    void merge(int a, int b){
        a = get(a); b = get(b); if (a == b) return;
        adj[id].push_back(a); adj[id].push_back(b);
        par[a] = par[b] = id++;
    }
    void dfs(int i){
        tin[i] = ti++;
        for (int x : adj[i]) dfs(x);
        tout[i] = ti - 1;
    }
};
struct segTree{
    multiset<int> seg[mx * 2]; 
    void upd(int i, int num){
        for (i += mx; i; i /= 2) seg[i].insert(num);
    }
    bool qry(int l, int r, int a, int b){
        bool ans = 0;
        auto chk = [&](int i){ 
            auto it = seg[i].lower_bound(a);
            return it != seg[i].end() and *it <= b;
        };
        for (l += mx, r += mx; l <= r and !ans; r /= 2, l /= 2){
            if (l % 2 == 1) ans |= chk(l++);
            if (r % 2 == 0) ans |= chk(r--);
        }
        return ans;
    }
};
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];
    
    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);

    dsuTree TL(n), TR(n); vi st1(q), st2(q), ans(q);

    for (int i = n - 1; ~i; i--){
        for (int x : adj[i]) if (x > i) TL.merge(i, x); 
        for (int qry : QL[i]) st1[qry] = TL.get(S[qry]);
    }
    for (int i = 0; i < n; i++){
        for (int x : adj[i]) if (x < i) TR.merge(i, x);
        for (int qry : QR[i]) st2[qry] = TR.get(E[qry]);
    }
    TL.dfs(TL.id - 1); TR.dfs(TR.id - 1); segTree seg;

    for (int i = 0; i < n; i++) 
        seg.upd(TL.tin[i], TR.tin[i]);
    for (int i = 0; i < q; i++)
        ans[i] = seg.qry(TL.tin[st1[i]], TL.tout[st1[i]], TR.tin[st2[i]], TR.tout[st2[i]]);
    
    return ans;
}

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