Submission #777157

#	Time	Username	Problem	Language	Result	Execution time	Memory
777157		GusterGoose27	Werewolf (IOI18_werewolf)	C++17	15 / 100	1911 ms	473272 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];
int id[2*MAXN];

void make_decomp() {
    for (int i = n; i < 2*n; i++) id[i] = order[i-n];
    for (int i = 1; i < n; i++) {
        id[i] = t++;
    }
    for (int i = n; i < 2*n; i++) {
        for (int cur = i; cur > 0; cur /= 2) {
            cont[order[i-n]].insert(id[cur]);
        }
        // cerr << order[i-n] << ": \n";
        // for (int v: cont[order[i-n]]) cerr << v << ' ';
        // cerr << '\n';
    }
    for (int i = 0; i < q; i++) {
        for (int l = range[tree_node[i]].first+n, r = range[tree_node[i]].second+1+n; r > l; l /= 2, r /= 2) {
            if (l & 1) query_nodes[i].push_back(id[l++]);
            if (r & 1) query_nodes[i].push_back(id[--r]);
        }
    }
}

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(); // 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);
    // }
    make_decomp();
    // 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: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51