Submission #569010

#	Time	Username	Problem	Language	Result	Execution time	Memory
569010		ngpin04	Werewolf (IOI18_werewolf)	C++17	100 / 100	1405 ms	173772 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 4e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

struct DSU {
    int n,node,timer;
    vector <int> par;
    vector <int> tin,tout;
    vector <vector <int>> adj;

    DSU(int _n = 0) {
        n = _n;
        par.assign(2 * n + 5, -1);
        adj.resize(2 * n + 5);
        tin.assign(2 * n + 5, 0);
        tout.assign(2 * n + 5, 0);
        node = n;
    }

    int getpar(int u) {
        return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
    }

    void join(int u, int v) {
        u = getpar(u);
        v = getpar(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return;
        adj[node].push_back(u);
        adj[node].push_back(v);
        par[u] = par[v] = node;
        node++;
    }    

    void dfs(int u) {
        // cerr << "dfs " << u << " " << timer << "\n";
        if (u < n) 
            tin[u] = ++timer;

        for (int v : adj[u]) {
            dfs(v);
            if (!tin[u])
                tin[u] = tin[v];
        }

        tout[u] = timer;
    }

    void build() {
        timer = 0;
        dfs(node - 1);
        for (int i = 0; i < node; i++)
            par[i] = -1;
        node = n;
    }

    pair <int, int> gettree(int u) {
        // cerr << "get tree " << u << " ";
        u = getpar(u);
        // cerr << u << " " << tin[u] << " " << tout[u] << "\n";
        return mp(tin[u], tout[u]);
    }
};

DSU pre, suf;

vector <int> st[N << 2];
vector <int> ed[N];
vector <int> qr[N];


pair <int, int> range[N][2];

int tin[N][2];
int ans[N];
int x[N];
int y[N];
int s[N];
int t[N];
int l[N];
int r[N];
int n,m,q;

void update(int id, int l, int r, int pos, int val) {
    if (l > pos || r < pos)
        return;
    st[id].push_back(val);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, pos, val);
    update(id << 1 | 1, mid + 1, r, pos, val);
}

void update(int pos, int val) {
    update(1, 1, n, pos, val);
}

int getans(int id, int l, int r, int u, int v, int x, int y) {
    if (l > v || r < u)
        return 0;
    if (l >= u && r <= v) {
        auto it = lower_bound(ALL(st[id]), x);
        return (it != st[id].end() && *it <= y);
    }
    int mid = (l + r) >> 1;
    int lnode = getans(id << 1, l, mid, u, v, x, y);
    int rnode = getans(id << 1 | 1, mid + 1, r, u, v, x, y);
    return lnode | rnode;
}

int getans(int l, int r, int x, int y) {
    return getans(1, 1, n, l, r, x, y);
}

void build() {
    pre = suf = DSU(n);
    for (int i = 0; i < m; i++) 
        if (x[i] > y[i])
            swap(x[i], y[i]);

    for (int i = 0; i < m; i++) 
        ed[y[i]].push_back(x[i]);

    for (int i = 0; i < q; i++)
        qr[r[i]].push_back(i);

    for (int i = 0; i < n; i++) 
    for (int j : ed[i])
        pre.join(i, j);
    
    pre.build();

    for (int i = 0; i < n; i++) {
        for (int j : ed[i])
            pre.join(i, j);

        for (int ind : qr[i]) 
            range[ind][0] = pre.gettree(t[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][0] = pre.tin[i];

    // process suffix 
    for (int i = 0; i < n; i++)
        qr[i].clear(), ed[i].clear();

    for (int i = 0; i < m; i++)
        ed[x[i]].push_back(y[i]);

    for (int i = 0; i < q; i++)
        qr[l[i]].push_back(i);

    for (int i = n - 1; i >= 0; i--) 
    for (int j : ed[i])
        suf.join(i, j);

    suf.build();

    for (int i = n - 1; i >= 0; i--) {
        for (int j : ed[i]) 
            suf.join(i, j);

        for (int ind : qr[i]) 
            range[ind][1] = suf.gettree(s[ind]);
    }

    for (int i = 0; i < n; i++)
        tin[i][1] = suf.tin[i];
}  

void solve() {
    for (int i = 0; i < n; i++)
        update(tin[i][0], tin[i][1]);

    for (int i = 1; i <= 4 * n; i++)
        sort(ALL(st[i]));

    for (int i = 0; i < q; i++) {
        auto [l, r] = range[i][0];
        auto [u, v] = range[i][1];
        // cerr << l << " " << r << " " << u << " " << v << "\n";
        ans[i] = getans(l, r, u, v);
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = N;
    m = X.size();
    for (int i = 0; i < m; i++)
        x[i] = X[i], y[i] = Y[i];

    q = S.size();
    for (int i = 0; i < q; i++) {
        s[i] = S[i];
        t[i] = E[i];
        l[i] = L[i];
        r[i] = R[i];
    }

    build();
    solve();
    vector <int> res;
    for (int i = 0; i < q; i++)
        res.push_back(ans[i]);
    return res;
}

//#include "grader.cpp"

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