제출 #936159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936159		GrindMachine	늑대인간 (IOI18_werewolf)	C++17	100 / 100	599 ms	126976 KiB

werewolf

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

check if there is at least 1 common node in the:
cc of s in the subgraph induced by nodes >= l and
cc of t in the subgraph induced by nodes <= r

key idea:
build a tree s.t any induced subgraph of nodes >= l for a given s forms a connected subtree

how to do this?
add nodes into a dsu in dec ord of indices
let's say u has effective edges to v1,v2,...,vk
connect u to the min value node in each of the components of v1,v2,...,vk

what does the induced subgraph for (s,l) look like?
in the tree, par(u) < u
keep going up from s as long as the node is >= l
let's say we stop at s'
par(s') < l, so we can only visit nodes in the subtree of s'
s' >= l, so everybody in the subtree >= l, so we can indeed visit everyone in the subtree of s'

a similar tree can be built for nodes in inc ord of indices (to calculate (t,r))

check if the subtree of u in tree1 and the subtree of v in tree2 have at least 1 node in common
answer queries offline
run a dfs for both trees and calculate tin,tout times
when at a node u in tree1, find the set of tin2[v] times for all nodes in the subtree of u in tree1
sets can be maintained efficiently using small to large merging
answer all queries at node u:
check if there exists a value x s.t l <= x <= r
=> can be done with set.lower_bound()

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int LOG = 18;

#include "werewolf.h"

struct DSU {
    vector<int> par, rankk, siz, mn, mx;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        mn = vector<int>(n + 1);
        mx = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
        mn[u] = u;
        mx[u] = u;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
        amin(mn[u],mn[v]);
        amax(mx[u],mx[v]);
    }
};

vector<int> adjg[N], adj1[N], adj2[N];
vector<int> tin1(N), tout1(N), subsiz1(N);
vector<int> tin2(N), tout2(N), subsiz2(N);
int up1[N][LOG], up2[N][LOG];
int timer;

void dfs1(int u){
    tin1[u] = timer++;
    subsiz1[u] = 1;
    trav(v,adj1[u]){
        up1[v][0] = u;
        rep1(j,LOG-1){
            up1[v][j] = up1[up1[v][j-1]][j-1];
        }
        dfs1(v);
        subsiz1[u] += subsiz1[v];
    }
    tout1[u] = timer++;
}

void dfs2(int u){
    tin2[u] = timer++;
    subsiz2[u] = 1;
    trav(v,adj2[u]){
        up2[v][0] = u;
        rep1(j,LOG-1){
            up2[v][j] = up2[up2[v][j-1]][j-1];
        }
        dfs2(v);
        subsiz2[u] += subsiz2[v];
    }
    tout2[u] = timer++;
}

set<ll> st[N];
vector<array<int,3>> queries_here[N];
vector<int> ans;

void dfs3(int u){
    pii big = {-1,-1};
    trav(v,adj1[u]){
        pii px = {subsiz1[v],v};
        amax(big,px);
    }

    int heavy = big.ss;
    if(heavy != -1){
        dfs3(heavy);
        swap(st[u],st[heavy]);
    }

    trav(v,adj1[u]){
        if(v == heavy) conts;
        dfs3(v);
        trav(x,st[v]){
            st[u].insert(x);
        }
        st[v].clear();
    }

    st[u].insert(tin2[u]);

    for(auto [l,r,id] : queries_here[u]){
        auto it = st[u].lower_bound(l);
        if(it != st[u].end()){
            if(*it <= r){
                ans[id] = 1;
            }
        }
    }
}

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> T,
                                std::vector<int> L, std::vector<int> R) {

    int m = sz(X), q = sz(S);
    rep(i,m){
        int u = X[i], v = Y[i];
        adjg[u].pb(v), adjg[v].pb(u);
    }

    DSU dsu(n);

    rev(u,n-1,0){
        trav(v,adjg[u]){
            if(u <= v){
                if(!dsu.same(u,v)){
                    int cc = dsu.find(v);
                    int mn = dsu.mn[cc];
                    adj1[u].pb(mn);
                    dsu.merge(u,v);
                }
            }
        }
    }

    dsu = DSU(n);

    rep(u,n){
        trav(v,adjg[u]){
            if(u >= v){
                if(!dsu.same(u,v)){
                    int cc = dsu.find(v);
                    int mx = dsu.mx[cc];
                    adj2[u].pb(mx);
                    dsu.merge(u,v);
                }
            }
        }
    }

    rep(j,LOG) up1[0][j] = 0;
    timer = 1;
    dfs1(0);

    rep(j,LOG) up2[n-1][j] = n-1;
    timer = 1;
    dfs2(n-1);

    ans = vector<int>(q);

    rep(i,q){
        int s = S[i], t = T[i], l = L[i], r = R[i];
        rev(j,LOG-1,0){
            if(up1[s][j] >= l){
                s = up1[s][j];
            }
        }
        rev(j,LOG-1,0){
            if(up2[t][j] <= r){
                t = up2[t][j];
            }
        }

        queries_here[s].pb({tin2[t],tout2[t],i});
    }

    dfs3(0);

    return ans;
}

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