Submission #777150

#	Time	Username	Problem	Language	Result	Execution time	Memory
777150		GusterGoose27	Werewolf (IOI18_werewolf)	C++17	0 / 100	1065 ms	522508 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5+5;

typedef pair<int, int> pii;

int n, m, q;
vector<int> edges[MAXN];
vector<int> dsutree[MAXN];
int uf[MAXN];
int order[MAXN];
pii range[MAXN];
vector<int> query_nodes[MAXN];
vector<int> uf2;
vector<int> lquery[MAXN];
vector<int> rquery[MAXN];
int tree_node[MAXN];
int t = 0;

int find(int i) {
    return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void merge(int i, int j) {
    j = find(j);
    if (i == j) return;
    assert(i > j);
    uf[j] = i;
    dsutree[i].push_back(j);
}

class stree;

unordered_set<int> cont[MAXN];

class stree {
public:
    int lp, rp;
    stree *l = nullptr;
    stree *r = nullptr;
    int id;
    stree(int lv, int rv) {
        lp = lv;
        rp = rv;
        if (lp < rp) {
            int mid = (lp+rp)/2;
            l = new stree(lp, mid);
            r = new stree(mid+1, rp);
            id = t++;
        }
        else id = order[lp];
        for (int i = lp; i <= rp; i++) {
            cont[order[i]].insert(id);
        }
    }
    void decompose(int lv, int rv, vector<int> &v) {
        if (lp > rv || rp < lv) return;
        if (lp >= lv && rp <= rv) {
            v.push_back(id);
            return;
        }
        l->decompose(lv, rv, v);
        r->decompose(lv, rv, v);
    }
};

stree *tree;

void dfs(int cur) {
    range[cur].first = t;
    order[t++] = cur;
    for (int nxt: dsutree[cur]) dfs(nxt);
    range[cur].second = t-1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
    q = S.size();
    n = N;
    m = X.size();
    for (int i = 0; i < q; i++) {
        lquery[L[i]].push_back(i);
        rquery[R[i]].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        edges[X[i]].push_back(Y[i]);
        edges[Y[i]].push_back(X[i]);
    }
    iota(uf, uf+n, 0);
    for (int i = 0; i < n; i++) {
        for (int nxt: edges[i]) {
            if (nxt > i) continue;
            merge(i, nxt);
        }
        for (int v: rquery[i]) tree_node[v] = find(E[v]);
    }
    dfs(n-1);
    // assert(false);
    tree = new stree(0, n-1); // really thick
    // assert(false);
    for (int i = 0; i < q; i++) {
        tree->decompose(range[tree_node[i]].first, range[tree_node[i]].second, query_nodes[i]);
        assert(query_nodes[i].size() < 40);
    }
    assert(false);
    iota(uf, uf+n, 0);
    for (int i = 0; i < n; i++) {
        assert(cont[i].find(i) != cont[i].end());
        assert(cont[i].size() < 20);
    }
    vector<int> ans(q, 0);
    for (int i = n-1; i >= 0; i--) {
        for (int nxt: edges[i]) {
            if (nxt < i) continue;
            int v = uf[nxt];
            int u = uf[i];
            if (u == v) continue;
            if (cont[u].size() < cont[v].size()) swap(u, v);
            for (int val: cont[v]) {
                cont[u].insert(val);
                uf[val] = u;
            }
            cont[v].clear();
        }
        for (int v: lquery[i]) {
            for (int check: query_nodes[v]) {
                if (cont[uf[S[v]]].find(check) != cont[uf[S[v]]].end()) {
                    ans[v] = 1;
                    break;
                }
            }
        }
    }
    return ans;
}

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