oj.uz

Submission #590844

# Submission time Handle Problem Language Result Execution time Memory
590844 2022-07-06T12:16:16 Z Namnamseo Stray Cat (JOI20_stray) C++17
4 / 100
 61 ms 24644 KB 
#include "Anthony.h"
#include <bitset>
#include <vector>
using namespace std;
using vi=vector<int>;

namespace {
const int maxn = int(2e4) + 10;

int n;

struct Edge { int l, r; } ev[maxn];
vector<int> es[maxn];
int par[maxn], pei[maxn];
int lev[maxn];
int col[maxn];

void bfs() {
    static int q[maxn];
    static bitset<maxn> vis;
    int f = 0, t = 1; vis.set(0);
    while (f < t) {
        int x = q[f++];
        for (int ei : es[x]) {
            int y = ev[ei].l + ev[ei].r - x;
            if (vis[y]) continue;
            vis.set(y);
            par[y] = x; pei[y] = ei; lev[y] = lev[x]+1;
            q[t++] = y;
        }
    }
}

vi Case1(int N, int M, vi U, vi V) {
    n = N;
    for (int i=0; i<M; ++i) {
        ev[i] = {U[i], V[i]};
        es[U[i]].push_back(i);
        es[V[i]].push_back(i);
    }
    bfs();
    for (int i=0; i<M; ++i) {
        int a = ev[i].l, b = ev[i].r;
        if (lev[a] == lev[b]) {
            col[i] = (lev[a]+1)%3;
            continue;
        }
        col[i] = min(lev[a], lev[b])%3;
    }
    for (int i=1; i<N; ++i) {
        int d = lev[i], d1 = (d+1)%3;
        int pc = 0, pei;
        for (int ei : es[i]) {
            auto &e = ev[ei];
            if (col[ei] == d1 && lev[e.l+e.r-i] == d)
                ++pc, pei = ei;
        }
        if (pc == 1) {
            col[pei] = d%3;
        }
    }
    return vi(col, col+M);
}

}  // namespace

vi Mark(int N, int M, int A, int B, vi U, vi V) {
    if (B == 0) return Case1(N, M, U, V);
    return {};
}

#include "Catherine.h"
#include <cassert>
#include <vector>
using namespace std;
using vi=vector<int>;

namespace {
int A, B;

int Move1(vi &y) {
    int oc = 0;
    for (int i=0; i<3; ++i) if (y[i] == 1) ++oc;
    if (oc == 1) for (int i=0; i<3; ++i) if (y[i] == 1) return i;
    assert(oc == 2);

    int tmp = 0;
    for (int i=0; i<3; ++i) if (y[i] == 1) tmp += i;
    tmp += 2;
    tmp *= 2;
    return tmp % 3;
}

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
}

int Move(vi y) {
    if (B == 0) return Move1(y);
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15988 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 37 ms 15276 KB Output is correct
4 Correct 49 ms 17112 KB Output is correct
5 Correct 53 ms 17164 KB Output is correct
6 Correct 35 ms 15808 KB Output is correct
7 Correct 47 ms 15928 KB Output is correct
8 Correct 41 ms 16676 KB Output is correct
9 Correct 55 ms 16580 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15988 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 37 ms 15276 KB Output is correct
4 Correct 49 ms 17112 KB Output is correct
5 Correct 53 ms 17164 KB Output is correct
6 Correct 35 ms 15808 KB Output is correct
7 Correct 47 ms 15928 KB Output is correct
8 Correct 41 ms 16676 KB Output is correct
9 Correct 55 ms 16580 KB Output is correct
10 Correct 43 ms 13784 KB Output is correct
11 Runtime error 51 ms 24644 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13580 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 28 ms 13036 KB Output is correct
4 Correct 49 ms 14884 KB Output is correct
5 Correct 45 ms 15072 KB Output is correct
6 Correct 37 ms 13600 KB Output is correct
7 Correct 36 ms 13596 KB Output is correct
8 Correct 44 ms 14252 KB Output is correct
9 Correct 44 ms 14248 KB Output is correct
10 Correct 43 ms 14076 KB Output is correct
11 Correct 39 ms 13980 KB Output is correct
12 Correct 43 ms 13896 KB Output is correct
13 Correct 42 ms 13940 KB Output is correct
14 Correct 61 ms 14292 KB Output is correct
15 Correct 39 ms 14268 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13580 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 28 ms 13036 KB Output is correct
4 Correct 49 ms 14884 KB Output is correct
5 Correct 45 ms 15072 KB Output is correct
6 Correct 37 ms 13600 KB Output is correct
7 Correct 36 ms 13596 KB Output is correct
8 Correct 44 ms 14252 KB Output is correct
9 Correct 44 ms 14248 KB Output is correct
10 Correct 43 ms 14076 KB Output is correct
11 Correct 39 ms 13980 KB Output is correct
12 Correct 43 ms 13896 KB Output is correct
13 Correct 42 ms 13940 KB Output is correct
14 Correct 61 ms 14292 KB Output is correct
15 Correct 39 ms 14268 KB Output is correct
16 Correct 31 ms 12144 KB Output is correct
17 Runtime error 34 ms 20912 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1072 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1512 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1724 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -