oj.uz

Submission #777145

# Submission time Handle Problem Language Result Execution time Memory
777145 2023-07-08T17:48:24 Z GusterGoose27 Werewolf (IOI18_werewolf) C++17
15 / 100
 3042 ms 524288 KB 
#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);
    }
    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34772 KB Output is correct
2 Correct 18 ms 34772 KB Output is correct
3 Correct 18 ms 34740 KB Output is correct
4 Correct 22 ms 34772 KB Output is correct
5 Correct 20 ms 34752 KB Output is correct
6 Correct 19 ms 34772 KB Output is correct
7 Correct 18 ms 34772 KB Output is correct
8 Correct 18 ms 34780 KB Output is correct
9 Correct 20 ms 34772 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34772 KB Output is correct
2 Correct 18 ms 34772 KB Output is correct
3 Correct 18 ms 34740 KB Output is correct
4 Correct 22 ms 34772 KB Output is correct
5 Correct 20 ms 34752 KB Output is correct
6 Correct 19 ms 34772 KB Output is correct
7 Correct 18 ms 34772 KB Output is correct
8 Correct 18 ms 34780 KB Output is correct
9 Correct 20 ms 34772 KB Output is correct
10 Correct 28 ms 37588 KB Output is correct
11 Correct 27 ms 37516 KB Output is correct
12 Correct 29 ms 37628 KB Output is correct
13 Correct 30 ms 37892 KB Output is correct
14 Correct 32 ms 38212 KB Output is correct
15 Correct 33 ms 37588 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 3042 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 34772 KB Output is correct
2 Correct 18 ms 34772 KB Output is correct
3 Correct 18 ms 34740 KB Output is correct
4 Correct 22 ms 34772 KB Output is correct
5 Correct 20 ms 34752 KB Output is correct
6 Correct 19 ms 34772 KB Output is correct
7 Correct 18 ms 34772 KB Output is correct
8 Correct 18 ms 34780 KB Output is correct
9 Correct 20 ms 34772 KB Output is correct
10 Correct 28 ms 37588 KB Output is correct
11 Correct 27 ms 37516 KB Output is correct
12 Correct 29 ms 37628 KB Output is correct
13 Correct 30 ms 37892 KB Output is correct
14 Correct 32 ms 38212 KB Output is correct
15 Correct 33 ms 37588 KB Output is correct
16 Runtime error 3042 ms 524288 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -