oj.uz

Submission #748708

# Submission time Handle Problem Language Result Execution time Memory
748708 2023-05-26T18:36:09 Z piOOE Stray Cat (JOI20_stray) C++17
15 / 100
 50 ms 16428 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    std::vector<int> X(M, -1);
    vector<vector<pair<int, int>>> adj(N);

    for (int i = 0; i < M; ++i) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }

    vector<int> dist(N, -1), par(N), e(N, -1), ord;
    dist[0] = 0;
    queue<int> q;
    q.push(0);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        ord.push_back(v);

        for (auto [to, i] : adj[v]) {
            if (dist[to] == -1) {
                dist[to] = dist[v] + 1;
                par[to] = v;
                e[to] = i;
                q.push(to);
            }
        }
    }

    if (A >= 3) {
        for (int i = 0; i < M; ++i) {
            if (dist[U[i]] > dist[V[i]]) {
                swap(U[i], V[i]);
            }
            X[i] = dist[U[i]] % 3;
        }
    } else {
        vector<int> code{0, 1, 0, 0, 1, 1};
        vector<int> dp(N, -1);

        for (int x : ord) {
            if (par[x] && adj[par[x]].size() >= 3) {
                if (X[e[par[x]]] == 1) {
                    dp[x] = 0;
                } else {
                    dp[x] = 1;
                }
            } else if (x == 0) {
                dp[x] = -1;
            } else {
                dp[x] = (1 + dp[par[x]]) % size(code);
            }

            if (dp[x] >= 0) {
                X[e[x]] = code[dp[x]];
            }
        }
    }

    assert(find(X.begin(), X.end(), -1) == X.end());

    return X;
}

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;


namespace {
    string code = "010011", adj;
    int A, B, e = -1;
    bool known = false;
}

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

int Move(std::vector<int> y) {
    vector<int> yy = y;

    if (e != -1) {
        yy[e] += 1;
    }

    int deg = accumulate(yy.begin(), yy.end(), 0);

    if (A >= 3) {
        int fi = -1, se = -1, cnt = 0;

        for (int i = 0; i < A; ++i) {
            if (yy[i]) {
                fi = fi == -1 ? i : fi;
                se = i;
                cnt += 1;
            }
        }

        if (fi != 0 || se != 2) {
            return e = fi;
        } else {
            return e = se;
        }
    } else {
        if (deg == 2) {
            if (known) {
                return e = find(y.begin(), y.end(), 1) - y.begin();
            }

            for (int i = 0; i < A; ++i) {
                adj += string(y[i], char('0' + i));
            }

            if (adj.size() == 5) {
                known = true;
                string s = code + code;

                for (int i = 0; i < 6; ++i) {
                    if (adj == s.substr(i, 5)) {
                        return -1;
                    }
                }

                return e = find(yy.begin(), yy.end(), 1) - yy.begin();
            } else {
                return e = adj.back() - '0';
            }
        } else {
            known = true;
            int u = find(yy.begin(), yy.end(), 1) - yy.begin();
            return u == e ? -1 : e = u;
        }
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15516 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 33 ms 14800 KB Output is correct
4 Correct 50 ms 16360 KB Output is correct
5 Correct 49 ms 16428 KB Output is correct
6 Correct 38 ms 15240 KB Output is correct
7 Correct 40 ms 15148 KB Output is correct
8 Correct 46 ms 15868 KB Output is correct
9 Correct 46 ms 15972 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15516 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 33 ms 14800 KB Output is correct
4 Correct 50 ms 16360 KB Output is correct
5 Correct 49 ms 16428 KB Output is correct
6 Correct 38 ms 15240 KB Output is correct
7 Correct 40 ms 15148 KB Output is correct
8 Correct 46 ms 15868 KB Output is correct
9 Correct 46 ms 15972 KB Output is correct
10 Correct 36 ms 13228 KB Output is correct
11 Correct 41 ms 13264 KB Output is correct
12 Correct 34 ms 13304 KB Output is correct
13 Correct 34 ms 13264 KB Output is correct
14 Correct 34 ms 13500 KB Output is correct
15 Correct 50 ms 13848 KB Output is correct
16 Correct 49 ms 16040 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12972 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 32 ms 12544 KB Output is correct
4 Correct 45 ms 14248 KB Output is correct
5 Correct 44 ms 14312 KB Output is correct
6 Correct 34 ms 13020 KB Output is correct
7 Correct 34 ms 12984 KB Output is correct
8 Correct 39 ms 13696 KB Output is correct
9 Correct 39 ms 13716 KB Output is correct
10 Correct 38 ms 13324 KB Output is correct
11 Correct 38 ms 13432 KB Output is correct
12 Correct 37 ms 13428 KB Output is correct
13 Correct 38 ms 13508 KB Output is correct
14 Correct 39 ms 13808 KB Output is correct
15 Correct 40 ms 13796 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12972 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 32 ms 12544 KB Output is correct
4 Correct 45 ms 14248 KB Output is correct
5 Correct 44 ms 14312 KB Output is correct
6 Correct 34 ms 13020 KB Output is correct
7 Correct 34 ms 12984 KB Output is correct
8 Correct 39 ms 13696 KB Output is correct
9 Correct 39 ms 13716 KB Output is correct
10 Correct 38 ms 13324 KB Output is correct
11 Correct 38 ms 13432 KB Output is correct
12 Correct 37 ms 13428 KB Output is correct
13 Correct 38 ms 13508 KB Output is correct
14 Correct 39 ms 13808 KB Output is correct
15 Correct 40 ms 13796 KB Output is correct
16 Correct 28 ms 11352 KB Output is correct
17 Correct 28 ms 11372 KB Output is correct
18 Correct 34 ms 11392 KB Output is correct
19 Correct 34 ms 11320 KB Output is correct
20 Correct 36 ms 11948 KB Output is correct
21 Correct 36 ms 11692 KB Output is correct
22 Correct 39 ms 13792 KB Output is correct
23 Correct 33 ms 11472 KB Output is correct
24 Correct 37 ms 11440 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 1 ms 560 KB Output is correct
3 Correct 2 ms 892 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Incorrect 2 ms 896 KB Wrong Answer [3]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11380 KB Output is correct
2 Correct 36 ms 11528 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 29 ms 11044 KB Output is correct
5 Correct 45 ms 12304 KB Output is correct
6 Correct 41 ms 12244 KB Output is correct
7 Correct 33 ms 11412 KB Output is correct
8 Incorrect 33 ms 11296 KB Wrong Answer [3]
9 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11336 KB Output is correct
2 Correct 36 ms 11528 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 31 ms 11104 KB Output is correct
5 Correct 41 ms 12212 KB Output is correct
6 Correct 41 ms 12200 KB Output is correct
7 Incorrect 29 ms 11348 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -