oj.uz

답안 #1038103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038103 2024-07-29T12:57:05 Z RecursiveCo 늑대인간 (IOI18_werewolf) C++17
34 / 100
 406 ms 61240 KB 
#include <bits/stdc++.h>

using namespace std;

#define in(i) cin >> i
#define out(o) cout << o

vector<int> parent;
vector<int> sz;

int find(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find(parent[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    parent[a] = b;
    sz[b] += sz[a];
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int M = X.size(); // = Y.size()
    int Q = S.size(); // = E.size() = L.size() = R.size()
    parent.resize(N);
    sz.resize(N, 1);
    vector<int> ans(Q);
    if (N <= 3000 && M <= 6000 && Q <= 3000 && false) {
        // S1, S2
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            int s = S[i];
            int e = E[i];

            for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
            for (int j = 0; j < M; j++) {
                int x = X[j];
                int y = Y[j];
                if (l <= min(x, y)) unite(x, y);
            }
            vector<int> works(N, 0);
            for (int j = 0; j < N; j++) if (find(s) == find(j)) works[j]++;

            for (int j = 0; j < N; j++) parent[j] = j, sz[j] = 1;
            for (int j = 0; j < M; j++) {
                int x = X[j];
                int y = Y[j];
                if (r >= max(x, y)) unite(x, y);
            }
            for (int j = 0; j < N; j++) if (find(e) == find(j)) works[j]++;
            ans[i] = +(*max_element(works.begin(), works.end()) == 2);
        }
    } else {
        // S3 assumed, if S4 then segfault or sth
        vector<vector<int>> adjList(N);
        for (int i = 0; i < M; i++) {
            int x = X[i];
            int y = Y[i];
            adjList[x].push_back(y);
            adjList[y].push_back(x);
        }
        int v = 0;
        int prev = -1;
        while (adjList[v].size() == 2) {
            if (adjList[v][0] == prev) {
                prev = v;
                v = adjList[v][1];
            } else {
                prev = v;
                v = adjList[v][0];
            }
        }
        vector<int> order;
        order.push_back(v);
        prev = -1;
        do {
            if (adjList[v][0] == prev) {
                prev = v;
                v = adjList[v][1];
            } else {
                prev = v;
                v = adjList[v][0];
            }
            order.push_back(v);
        } while (adjList[v].size() == 2);
        vector<int> ind(N);
        for (int i = 0; i < N; i++) {
            ind[order[i]] = i;
        }
        vector<int> left(Q);
        vector<int> right(Q);
        vector<array<int, 4>> human;
        vector<array<int, 4>> wolf;
        // {determiner, node, query index, left or right}. left = 0, right = 1.
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            int s = S[i];
            int e = E[i];
            int u = ind[s];
            int v = ind[e];
            if (u < v) {
                human.push_back({l, u, i, 1});
                wolf.push_back({r, v, i, 0});
            } else {
                human.push_back({l, u, i, 0});
                wolf.push_back({r, v, i, 1});
            }
        }
        sort(human.begin(), human.end());
        sort(wolf.rbegin(), wolf.rend());
        set<int> less;
        int ptr = 0;
        for (int i = 0; i < N; i++) {
            while (ptr < Q && human[ptr][0] <= i) {
                int l = human[ptr][0];
                int u = human[ptr][1];
                int j = human[ptr][2];
                int dir = human[ptr][3];
                if (dir) {
                    auto it = less.lower_bound(u);
                    if (it == less.end()) right[j] = N + 5;
                    else right[j] = (*it) - 1;
                } else {
                    auto it = less.lower_bound(u);
                    if (it == less.begin()) left[j] = -5;
                    else left[j] = (*--it) + 1;
                }
                ptr++;
            }
            less.insert(ind[i]);
        }
        set<int> more;
        ptr = 0;
        for (int i = N - 1; i >= 0; i--) {
            while (ptr < Q && wolf[ptr][0] >= i) {
                int l = wolf[ptr][0];
                int u = wolf[ptr][1];
                int j = wolf[ptr][2];
                int dir = wolf[ptr][3];
                if (dir) {
                    auto it = more.lower_bound(u);
                    if (it == more.end()) right[j] = N + 5;
                    else right[j] = (*it) - 1;
                } else {
                    auto it = more.lower_bound(u);
                    if (it == more.begin()) left[j] = -5;
                    else left[j] = (*--it) + 1;
                }
                ptr++;
            }
            more.insert(ind[i]);
        }
        for (int i = 0; i < Q; i++) {
            ans[i] = +(left[i] <= right[i]);
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:120:21: warning: unused variable 'l' [-Wunused-variable]
  120 |                 int l = human[ptr][0];
      |                     ^
werewolf.cpp:141:21: warning: unused variable 'l' [-Wunused-variable]
  141 |                 int l = wolf[ptr][0];
      |                     ^

Subtask #1
0 / 7.0

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

Subtask #2
0 / 8.0

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

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 406 ms 52644 KB Output is correct
2 Correct 276 ms 61240 KB Output is correct
3 Correct 295 ms 59556 KB Output is correct
4 Correct 321 ms 59612 KB Output is correct
5 Correct 299 ms 59652 KB Output is correct
6 Correct 342 ms 59544 KB Output is correct
7 Correct 312 ms 60120 KB Output is correct
8 Correct 292 ms 61148 KB Output is correct
9 Correct 247 ms 59784 KB Output is correct
10 Correct 272 ms 59612 KB Output is correct
11 Correct 266 ms 59668 KB Output is correct
12 Correct 306 ms 59696 KB Output is correct
13 Correct 230 ms 59612 KB Output is correct
14 Correct 238 ms 59616 KB Output is correct
15 Correct 230 ms 59648 KB Output is correct
16 Correct 234 ms 59612 KB Output is correct
17 Correct 306 ms 59676 KB Output is correct

Subtask #4
0 / 51.0

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