oj.uz

Submission #1038089

# Submission time Handle Problem Language Result Execution time Memory
1038089 2024-07-29T12:52:51 Z RecursiveCo Werewolf (IOI18_werewolf) C++17
15 / 100
 355 ms 24344 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) {
        // 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;
        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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 355 ms 604 KB Output is correct
11 Correct 316 ms 604 KB Output is correct
12 Correct 282 ms 600 KB Output is correct
13 Correct 337 ms 604 KB Output is correct
14 Correct 272 ms 604 KB Output is correct
15 Correct 339 ms 604 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 110 ms 24344 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 355 ms 604 KB Output is correct
11 Correct 316 ms 604 KB Output is correct
12 Correct 282 ms 600 KB Output is correct
13 Correct 337 ms 604 KB Output is correct
14 Correct 272 ms 604 KB Output is correct
15 Correct 339 ms 604 KB Output is correct
16 Runtime error 110 ms 24344 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -