oj.uz

Submission #590836

# Submission time Handle Problem Language Result Execution time Memory
590836 2022-07-06T12:12:49 Z Namnamseo Stray Cat (JOI20_stray) C++17
4 / 100
 75 ms 24356 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]) {
            if (col[ei] == d1) ++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 57 ms 15780 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 39 ms 15020 KB Output is correct
4 Correct 75 ms 16844 KB Output is correct
5 Correct 60 ms 16912 KB Output is correct
6 Correct 49 ms 15600 KB Output is correct
7 Correct 63 ms 15504 KB Output is correct
8 Correct 49 ms 16236 KB Output is correct
9 Correct 51 ms 16324 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 15780 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 39 ms 15020 KB Output is correct
4 Correct 75 ms 16844 KB Output is correct
5 Correct 60 ms 16912 KB Output is correct
6 Correct 49 ms 15600 KB Output is correct
7 Correct 63 ms 15504 KB Output is correct
8 Correct 49 ms 16236 KB Output is correct
9 Correct 51 ms 16324 KB Output is correct
10 Correct 55 ms 13600 KB Output is correct
11 Runtime error 54 ms 24356 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 39 ms 13364 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct
3 Correct 30 ms 12896 KB Output is correct
4 Correct 56 ms 14636 KB Output is correct
5 Correct 52 ms 14748 KB Output is correct
6 Correct 57 ms 13392 KB Output is correct
7 Correct 38 ms 13392 KB Output is correct
8 Correct 47 ms 13992 KB Output is correct
9 Correct 45 ms 14064 KB Output is correct
10 Correct 45 ms 13676 KB Output is correct
11 Correct 45 ms 13772 KB Output is correct
12 Correct 60 ms 13624 KB Output is correct
13 Correct 52 ms 13740 KB Output is correct
14 Correct 66 ms 13940 KB Output is correct
15 Correct 53 ms 13992 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13364 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct
3 Correct 30 ms 12896 KB Output is correct
4 Correct 56 ms 14636 KB Output is correct
5 Correct 52 ms 14748 KB Output is correct
6 Correct 57 ms 13392 KB Output is correct
7 Correct 38 ms 13392 KB Output is correct
8 Correct 47 ms 13992 KB Output is correct
9 Correct 45 ms 14064 KB Output is correct
10 Correct 45 ms 13676 KB Output is correct
11 Correct 45 ms 13772 KB Output is correct
12 Correct 60 ms 13624 KB Output is correct
13 Correct 52 ms 13740 KB Output is correct
14 Correct 66 ms 13940 KB Output is correct
15 Correct 53 ms 13992 KB Output is correct
16 Correct 34 ms 11712 KB Output is correct
17 Runtime error 41 ms 20664 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 1 ms 1024 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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