oj.uz

Submission #1038084

# Submission time Handle Problem Language Result Execution time Memory
1038084 2024-07-29T12:51:42 Z RecursiveCo Werewolf (IOI18_werewolf) C++17
15 / 100
 362 ms 24404 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);
        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:119:21: warning: unused variable 'l' [-Wunused-variable]
  119 |                 int l = human[ptr][0];
      |                     ^
werewolf.cpp:140:21: warning: unused variable 'l' [-Wunused-variable]
  140 |                 int l = wolf[ptr][0];
      |                     ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 358 ms 604 KB Output is correct
11 Correct 280 ms 600 KB Output is correct
12 Correct 280 ms 600 KB Output is correct
13 Correct 337 ms 604 KB Output is correct
14 Correct 274 ms 604 KB Output is correct
15 Correct 362 ms 604 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 87 ms 24404 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 358 ms 604 KB Output is correct
11 Correct 280 ms 600 KB Output is correct
12 Correct 280 ms 600 KB Output is correct
13 Correct 337 ms 604 KB Output is correct
14 Correct 274 ms 604 KB Output is correct
15 Correct 362 ms 604 KB Output is correct
16 Runtime error 87 ms 24404 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -