oj.uz

Submission #590834

# Submission time Handle Problem Language Result Execution time Memory
590834 2022-07-06T12:11:58 Z Namnamseo Stray Cat (JOI20_stray) C++17
4 / 100
 63 ms 17356 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 <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;

    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 63 ms 15584 KB Output is correct
2 Correct 1 ms 1072 KB Output is correct
3 Correct 34 ms 15480 KB Output is correct
4 Correct 59 ms 17280 KB Output is correct
5 Correct 55 ms 17356 KB Output is correct
6 Correct 36 ms 15972 KB Output is correct
7 Correct 51 ms 15988 KB Output is correct
8 Correct 60 ms 16688 KB Output is correct
9 Correct 48 ms 16812 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 15584 KB Output is correct
2 Correct 1 ms 1072 KB Output is correct
3 Correct 34 ms 15480 KB Output is correct
4 Correct 59 ms 17280 KB Output is correct
5 Correct 55 ms 17356 KB Output is correct
6 Correct 36 ms 15972 KB Output is correct
7 Correct 51 ms 15988 KB Output is correct
8 Correct 60 ms 16688 KB Output is correct
9 Correct 48 ms 16812 KB Output is correct
10 Correct 37 ms 14076 KB Output is correct
11 Incorrect 43 ms 13992 KB Wrong Answer [5]
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13324 KB Output is correct
2 Correct 1 ms 948 KB Output is correct
3 Correct 41 ms 13268 KB Output is correct
4 Correct 60 ms 15028 KB Output is correct
5 Correct 52 ms 15088 KB Output is correct
6 Correct 60 ms 13756 KB Output is correct
7 Correct 34 ms 13840 KB Output is correct
8 Correct 39 ms 14396 KB Output is correct
9 Correct 40 ms 14412 KB Output is correct
10 Correct 49 ms 14300 KB Output is correct
11 Correct 46 ms 14088 KB Output is correct
12 Correct 46 ms 14192 KB Output is correct
13 Correct 62 ms 14244 KB Output is correct
14 Correct 46 ms 14352 KB Output is correct
15 Correct 41 ms 14396 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13324 KB Output is correct
2 Correct 1 ms 948 KB Output is correct
3 Correct 41 ms 13268 KB Output is correct
4 Correct 60 ms 15028 KB Output is correct
5 Correct 52 ms 15088 KB Output is correct
6 Correct 60 ms 13756 KB Output is correct
7 Correct 34 ms 13840 KB Output is correct
8 Correct 39 ms 14396 KB Output is correct
9 Correct 40 ms 14412 KB Output is correct
10 Correct 49 ms 14300 KB Output is correct
11 Correct 46 ms 14088 KB Output is correct
12 Correct 46 ms 14192 KB Output is correct
13 Correct 62 ms 14244 KB Output is correct
14 Correct 46 ms 14352 KB Output is correct
15 Correct 41 ms 14396 KB Output is correct
16 Correct 30 ms 12196 KB Output is correct
17 Incorrect 30 ms 12168 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1020 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 1276 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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