oj.uz

Submission #1038105

# Submission time Handle Problem Language Result Execution time Memory
1038105 2024-07-29T12:57:30 Z RecursiveCo Werewolf (IOI18_werewolf) C++17
49 / 100
 401 ms 53208 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(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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 0 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 0 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 0 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 350 ms 604 KB Output is correct
11 Correct 324 ms 616 KB Output is correct
12 Correct 282 ms 600 KB Output is correct
13 Correct 301 ms 604 KB Output is correct
14 Correct 283 ms 604 KB Output is correct
15 Correct 401 ms 640 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 51164 KB Output is correct
2 Correct 229 ms 52392 KB Output is correct
3 Correct 236 ms 51168 KB Output is correct
4 Correct 295 ms 52700 KB Output is correct
5 Correct 254 ms 52960 KB Output is correct
6 Correct 325 ms 51164 KB Output is correct
7 Correct 313 ms 51352 KB Output is correct
8 Correct 233 ms 51164 KB Output is correct
9 Correct 247 ms 51164 KB Output is correct
10 Correct 275 ms 51672 KB Output is correct
11 Correct 285 ms 51368 KB Output is correct
12 Correct 312 ms 53208 KB Output is correct
13 Correct 249 ms 51364 KB Output is correct
14 Correct 246 ms 52440 KB Output is correct
15 Correct 250 ms 51168 KB Output is correct
16 Correct 274 ms 51936 KB Output is correct
17 Correct 335 ms 51352 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 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 0 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 350 ms 604 KB Output is correct
11 Correct 324 ms 616 KB Output is correct
12 Correct 282 ms 600 KB Output is correct
13 Correct 301 ms 604 KB Output is correct
14 Correct 283 ms 604 KB Output is correct
15 Correct 401 ms 640 KB Output is correct
16 Correct 360 ms 51164 KB Output is correct
17 Correct 229 ms 52392 KB Output is correct
18 Correct 236 ms 51168 KB Output is correct
19 Correct 295 ms 52700 KB Output is correct
20 Correct 254 ms 52960 KB Output is correct
21 Correct 325 ms 51164 KB Output is correct
22 Correct 313 ms 51352 KB Output is correct
23 Correct 233 ms 51164 KB Output is correct
24 Correct 247 ms 51164 KB Output is correct
25 Correct 275 ms 51672 KB Output is correct
26 Correct 285 ms 51368 KB Output is correct
27 Correct 312 ms 53208 KB Output is correct
28 Correct 249 ms 51364 KB Output is correct
29 Correct 246 ms 52440 KB Output is correct
30 Correct 250 ms 51168 KB Output is correct
31 Correct 274 ms 51936 KB Output is correct
32 Correct 335 ms 51352 KB Output is correct
33 Incorrect 221 ms 44368 KB Output isn't correct
34 Halted 0 ms 0 KB -