oj.uz

답안 #1038055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038055 2024-07-29T12:33:44 Z RecursiveCo 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 20368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 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 -