oj.uz

Submission #590856

# Submission time Handle Problem Language Result Execution time Memory
590856 2022-07-06T12:22:50 Z Namnamseo Stray Cat (JOI20_stray) C++17
4 / 100
 56 ms 24468 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();
    static int pec[maxn];
    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;
            ++pec[a]; ++pec[b];
        } else {
            col[i] = min(lev[a], lev[b])%3;
        }
    }
    static int q[maxn];
    int f = 0, t = 0;
    for (int i=0; i<N; ++i) if (pec[i] == 1) q[t++] = i;
    while (f < t) {
        int x = q[f++];
        if (pec[x] != 1) continue;
        int d = lev[x], d1 = (d+1)%3;
        for (int ei : es[x]) {
            auto &e = ev[ei];
            int y = e.l+e.r-x;
            if (col[ei] == d1 && lev[y] == d) {
                col[ei] = d%3;
                --pec[y];
                if (pec[y] == 1) q[t++] = y;
            }
        }
    }
    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 37 ms 15808 KB Output is correct
2 Correct 0 ms 1028 KB Output is correct
3 Correct 32 ms 15136 KB Output is correct
4 Correct 46 ms 16932 KB Output is correct
5 Correct 56 ms 16916 KB Output is correct
6 Correct 37 ms 15488 KB Output is correct
7 Correct 35 ms 15600 KB Output is correct
8 Correct 44 ms 16408 KB Output is correct
9 Correct 41 ms 16408 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15808 KB Output is correct
2 Correct 0 ms 1028 KB Output is correct
3 Correct 32 ms 15136 KB Output is correct
4 Correct 46 ms 16932 KB Output is correct
5 Correct 56 ms 16916 KB Output is correct
6 Correct 37 ms 15488 KB Output is correct
7 Correct 35 ms 15600 KB Output is correct
8 Correct 44 ms 16408 KB Output is correct
9 Correct 41 ms 16408 KB Output is correct
10 Correct 32 ms 13784 KB Output is correct
11 Runtime error 40 ms 24468 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 36 ms 13432 KB Output is correct
2 Correct 0 ms 1032 KB Output is correct
3 Correct 28 ms 13028 KB Output is correct
4 Correct 41 ms 14784 KB Output is correct
5 Correct 49 ms 14756 KB Output is correct
6 Correct 33 ms 13408 KB Output is correct
7 Correct 33 ms 13404 KB Output is correct
8 Correct 41 ms 13976 KB Output is correct
9 Correct 40 ms 14004 KB Output is correct
10 Correct 36 ms 13836 KB Output is correct
11 Correct 36 ms 13768 KB Output is correct
12 Correct 37 ms 13776 KB Output is correct
13 Correct 37 ms 13840 KB Output is correct
14 Correct 45 ms 14056 KB Output is correct
15 Correct 40 ms 14108 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13432 KB Output is correct
2 Correct 0 ms 1032 KB Output is correct
3 Correct 28 ms 13028 KB Output is correct
4 Correct 41 ms 14784 KB Output is correct
5 Correct 49 ms 14756 KB Output is correct
6 Correct 33 ms 13408 KB Output is correct
7 Correct 33 ms 13404 KB Output is correct
8 Correct 41 ms 13976 KB Output is correct
9 Correct 40 ms 14004 KB Output is correct
10 Correct 36 ms 13836 KB Output is correct
11 Correct 36 ms 13768 KB Output is correct
12 Correct 37 ms 13776 KB Output is correct
13 Correct 37 ms 13840 KB Output is correct
14 Correct 45 ms 14056 KB Output is correct
15 Correct 40 ms 14108 KB Output is correct
16 Correct 28 ms 11864 KB Output is correct
17 Runtime error 33 ms 20596 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 0 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 4 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 4 ms 1392 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -