oj.uz

Submission #1077395

# Submission time Handle Problem Language Result Execution time Memory
1077395 2024-08-27T06:45:27 Z vjudge1 Werewolf (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

# 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 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

# 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 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

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 ms 20808 KB Time limit exceeded
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 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 -