oj.uz

답안 #777139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777139 2023-07-08T17:43:35 Z GusterGoose27 늑대인간 (IOI18_werewolf) C++17
15 / 100
 3080 ms 519780 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;

set<int> cont[MAXN];

class stree {
public:
    int lp, rp;
    stree *l = nullptr;
    stree *r = nullptr;
    int id;
    stree(int lv, int rv, stree *p = nullptr) {
        lp = lv;
        rp = rv;
        if (lp < rp) {
            int mid = (lp+rp)/2;
            l = new stree(lp, mid, this);
            r = new stree(mid+1, rp, this);
            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);
    tree = new stree(0, n-1);
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33160 KB Output is correct
2 Correct 17 ms 33196 KB Output is correct
3 Correct 16 ms 33228 KB Output is correct
4 Correct 17 ms 33108 KB Output is correct
5 Correct 16 ms 33196 KB Output is correct
6 Correct 17 ms 33236 KB Output is correct
7 Correct 18 ms 33164 KB Output is correct
8 Correct 17 ms 33228 KB Output is correct
9 Correct 17 ms 33192 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33160 KB Output is correct
2 Correct 17 ms 33196 KB Output is correct
3 Correct 16 ms 33228 KB Output is correct
4 Correct 17 ms 33108 KB Output is correct
5 Correct 16 ms 33196 KB Output is correct
6 Correct 17 ms 33236 KB Output is correct
7 Correct 18 ms 33164 KB Output is correct
8 Correct 17 ms 33228 KB Output is correct
9 Correct 17 ms 33192 KB Output is correct
10 Correct 28 ms 36044 KB Output is correct
11 Correct 28 ms 36012 KB Output is correct
12 Correct 27 ms 35836 KB Output is correct
13 Correct 30 ms 36064 KB Output is correct
14 Correct 33 ms 36160 KB Output is correct
15 Correct 29 ms 36068 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3080 ms 519780 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33160 KB Output is correct
2 Correct 17 ms 33196 KB Output is correct
3 Correct 16 ms 33228 KB Output is correct
4 Correct 17 ms 33108 KB Output is correct
5 Correct 16 ms 33196 KB Output is correct
6 Correct 17 ms 33236 KB Output is correct
7 Correct 18 ms 33164 KB Output is correct
8 Correct 17 ms 33228 KB Output is correct
9 Correct 17 ms 33192 KB Output is correct
10 Correct 28 ms 36044 KB Output is correct
11 Correct 28 ms 36012 KB Output is correct
12 Correct 27 ms 35836 KB Output is correct
13 Correct 30 ms 36064 KB Output is correct
14 Correct 33 ms 36160 KB Output is correct
15 Correct 29 ms 36068 KB Output is correct
16 Runtime error 3080 ms 519780 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -