oj.uz

답안 #1077395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077395 2024-08-27T06:45:27 Z vjudge1 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 20808 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct DSU {
    vi e;
    DSU(int n) : e(n, -1) {}
    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        if(e[u] >= e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }

    bool same(int u, int v) {
        return repr(u) == repr(v);
    }
};

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R) {
    int q = (int)S.size(), m = (int)X.size();
    vi Re(q, 0);
    for(int nr = 0; nr < q; ++nr) {
        DSU St(n), Dr(n);
        for(int i = 0; i < m; ++i) {
            if(X[i] <= R[nr] && Y[i] <= R[nr])
                St.join(X[i], Y[i]);
            if(X[i] >= L[nr] && Y[i] >= L[nr])
                Dr.join(X[i], Y[i]);
        }
        for(int i = L[nr]; i <= R[nr]; ++i) {
            if(Dr.same(i, S[nr]) && St.same(i, E[nr])) Re[nr] = 1;
        }
    }
    return Re;
}

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 1 ms 348 KB Output is correct
4 Correct 1 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 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 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 262 ms 700 KB Output is correct
11 Correct 222 ms 600 KB Output is correct
12 Correct 178 ms 700 KB Output is correct
13 Correct 237 ms 600 KB Output is correct
14 Correct 174 ms 684 KB Output is correct
15 Correct 453 ms 788 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4033 ms 20808 KB Time limit exceeded
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 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 262 ms 700 KB Output is correct
11 Correct 222 ms 600 KB Output is correct
12 Correct 178 ms 700 KB Output is correct
13 Correct 237 ms 600 KB Output is correct
14 Correct 174 ms 684 KB Output is correct
15 Correct 453 ms 788 KB Output is correct
16 Execution timed out 4033 ms 20808 KB Time limit exceeded
17 Halted 0 ms 0 KB -