oj.uz

Submission #1038055

# Submission time Handle Problem Language Result Execution time Memory
1038055 2024-07-29T12:33:44 Z RecursiveCo Werewolf (IOI18_werewolf) C++17
15 / 100
 365 ms 20368 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);
        }
    }
    return ans;
}

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 440 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 440 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 365 ms 720 KB Output is correct
11 Correct 321 ms 604 KB Output is correct
12 Correct 254 ms 700 KB Output is correct
13 Correct 297 ms 712 KB Output is correct
14 Correct 256 ms 716 KB Output is correct
15 Correct 364 ms 796 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 20368 KB Output isn't correct
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 440 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 365 ms 720 KB Output is correct
11 Correct 321 ms 604 KB Output is correct
12 Correct 254 ms 700 KB Output is correct
13 Correct 297 ms 712 KB Output is correct
14 Correct 256 ms 716 KB Output is correct
15 Correct 364 ms 796 KB Output is correct
16 Incorrect 102 ms 20368 KB Output isn't correct
17 Halted 0 ms 0 KB -