Submission #543325

#	Time	Username	Problem	Language	Result	Execution time	Memory
543325		alextodoran	Werewolf (IOI18_werewolf)	C++17	100 / 100	773 ms	143132 KiB

werewolf

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
//#include "werewolf.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 400000;
const int Q_MAX = 200000;

int N, M, Q;
vector <vector <int>> adj;

struct DSU {
    vector <int> ancestor;
    vector <vector <int>> sons;
    int cntNodes;

    DSU () {
        cntNodes = N;
        ancestor = vector <int> (N, -1);
        sons = vector <vector <int>> (N);
    }
    int findRoot (int u) {
        return (ancestor[u] == -1 ? u : ancestor[u] = findRoot(ancestor[u]));
    }
    void join (int u, int v) {
        u = findRoot(u);
        v = findRoot(v);
        if (u != v) {
            int w = cntNodes++;
            sons.push_back({});
            ancestor.push_back(-1);
            sons[w].push_back(u);
            sons[w].push_back(v);
            ancestor[u] = w;
            ancestor[v] = w;
        }
    }
    vector <pair <int, int>> range;
    vector <int> order;
    int currID;
    void dfs (int u) {
        if (sons[u].empty()) {
            order.push_back(u);
            range[u] = make_pair(currID, currID);
            currID++;
        } else {
            range[u] = make_pair(INT_MAX, INT_MIN);
            for (int v : sons[u]) {
                dfs(v);
                range[u].first = min(range[u].first, range[v].first);
                range[u].second = max(range[u].second, range[v].second);
            }
        }
    }
    void linearize () {
        range = vector <pair <int, int>> (cntNodes);
        currID = 0;
        dfs(cntNodes - 1);
    }
};

vector <vector <int>> SGT;

void build (int node, int l, int r, vector <int> &arr) {
    SGT[node].resize(r - l + 1);
    if (l == r) {
        SGT[node][0] = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid, arr);
    build(rSon, mid + 1, r, arr);
    merge(SGT[lSon].begin(), SGT[lSon].end(), SGT[rSon].begin(), SGT[rSon].end(), SGT[node].begin());
}
void build (vector <int> &arr) {
    SGT = vector <vector <int>> (N * 4);
    build(1, 0, N - 1, arr);
}

bool query (int node, int l, int r, int ql, int qr, int mn, int mx) {
    if (ql <= l && r <= qr) {
        int lo = 0, hi = (int) SGT[node].size();
        while (lo < hi) {
            int avg = (lo + hi) / 2;
            if (SGT[node][avg] < mn) {
                lo = avg + 1;
            } else {
                hi = avg;
            }
        }
        return (lo < (int) SGT[node].size() && SGT[node][lo] <= mx);
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (ql <= mid) {
        if (query(lSon, l, mid, ql, qr, mn, mx) == true) {
            return true;
        }
    }
    if (mid + 1 <= qr) {
        if (query(rSon, mid + 1, r, ql, qr, mn, mx) == true) {
            return true;
        }
    }
    return false;
}
bool query (int ql, int qr, int mn, int mx) {
    return query(1, 0, N - 1, ql, qr, mn, mx);
}

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 = (int) X.size(); Q = (int) S.size();
    adj = vector <vector <int>> (N);
    for (int i = 0; i < M; i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }

    vector <vector <int>> withL(N), withR(N);
    for (int i = 0; i < Q; i++) {
        withL[L[i]].push_back(i);
        withR[R[i]].push_back(i);
    }

    vector <int> Lnode(Q), Rnode(Q);
    DSU DSULarge;
    for (int u = N - 1; u >= 0; u--) {
        for (int v : adj[u]) {
            if (u < v) {
                DSULarge.join(u, v);
            }
        }
        for (int i : withL[u]) {
            Lnode[i] = DSULarge.findRoot(S[i]);
        }
    }
    DSU DSUSmall;
    for (int u = 0; u < N; u++) {
        for (int v : adj[u]) {
            if (v < u) {
                DSUSmall.join(u, v);
            }
        }
        for (int i : withR[u]) {
            Rnode[i] = DSUSmall.findRoot(E[i]);
        }
    }
    DSULarge.linearize();
    DSUSmall.linearize();
    vector <pair <int, int>> Lrange(Q), Rrange(Q);
    for (int i = 0; i < Q; i++) {
        Lrange[i] = DSULarge.range[Lnode[i]];
        Rrange[i] = DSUSmall.range[Rnode[i]];
    }

    vector <int> arr(N);
    for (int u = 0; u < N; u++) {
        arr[DSULarge.range[u].first] = DSUSmall.range[u].first;
    }
    build(arr);
    vector <int> answer(Q);
    for (int i = 0; i < Q; i++) {
        answer[i] = query(Lrange[i].first, Lrange[i].second, Rrange[i].first, Rrange[i].second);
    }

    return answer;
}

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