oj.uz

Submission #748710

# Submission time Handle Problem Language Result Execution time Memory
748710 2023-05-26T18:40:17 Z piOOE Stray Cat (JOI20_stray) C++17
89 / 100
 59 ms 16288 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), dp(N, -1);
    dist[0] = 0;
    queue<int> q;
    q.push(0);

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

        if (A == 2) {
            int x = v;
            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]]) % 6;
            }

            if (dp[x] >= 0) {
                X[e[x]] = "010011"[dp[x]] - '0';
            }
        } else if (v > 0) {
            X[e[v]] = dist[par[v]] % 3;
        }

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

    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(y.begin(), y.end(), 1) - y.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 37 ms 15344 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 31 ms 14688 KB Output is correct
4 Correct 52 ms 16256 KB Output is correct
5 Correct 59 ms 16288 KB Output is correct
6 Correct 38 ms 14980 KB Output is correct
7 Correct 36 ms 15044 KB Output is correct
8 Correct 46 ms 15776 KB Output is correct
9 Correct 44 ms 15768 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15344 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 31 ms 14688 KB Output is correct
4 Correct 52 ms 16256 KB Output is correct
5 Correct 59 ms 16288 KB Output is correct
6 Correct 38 ms 14980 KB Output is correct
7 Correct 36 ms 15044 KB Output is correct
8 Correct 46 ms 15776 KB Output is correct
9 Correct 44 ms 15768 KB Output is correct
10 Incorrect 8 ms 2328 KB Wrong Answer [2]
11 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12912 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 33 ms 12444 KB Output is correct
4 Correct 48 ms 14072 KB Output is correct
5 Correct 47 ms 14192 KB Output is correct
6 Correct 32 ms 12872 KB Output is correct
7 Correct 33 ms 12864 KB Output is correct
8 Correct 38 ms 13532 KB Output is correct
9 Correct 41 ms 13504 KB Output is correct
10 Correct 37 ms 13236 KB Output is correct
11 Correct 40 ms 13220 KB Output is correct
12 Correct 37 ms 13184 KB Output is correct
13 Correct 46 ms 13256 KB Output is correct
14 Correct 49 ms 13548 KB Output is correct
15 Correct 43 ms 13568 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12912 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 33 ms 12444 KB Output is correct
4 Correct 48 ms 14072 KB Output is correct
5 Correct 47 ms 14192 KB Output is correct
6 Correct 32 ms 12872 KB Output is correct
7 Correct 33 ms 12864 KB Output is correct
8 Correct 38 ms 13532 KB Output is correct
9 Correct 41 ms 13504 KB Output is correct
10 Correct 37 ms 13236 KB Output is correct
11 Correct 40 ms 13220 KB Output is correct
12 Correct 37 ms 13184 KB Output is correct
13 Correct 46 ms 13256 KB Output is correct
14 Correct 49 ms 13548 KB Output is correct
15 Correct 43 ms 13568 KB Output is correct
16 Incorrect 8 ms 2448 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 904 KB Output is correct
7 Correct 2 ms 904 KB Output is correct
8 Correct 2 ms 904 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 2 ms 896 KB Output is correct
13 Correct 2 ms 896 KB Output is correct
14 Correct 2 ms 896 KB Output is correct
15 Correct 2 ms 896 KB Output is correct
16 Correct 2 ms 904 KB Output is correct
17 Correct 2 ms 904 KB Output is correct
18 Correct 2 ms 904 KB Output is correct
19 Correct 1 ms 896 KB Output is correct
20 Correct 2 ms 904 KB Output is correct
21 Correct 2 ms 896 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 904 KB Output is correct
24 Correct 2 ms 904 KB Output is correct
25 Correct 2 ms 904 KB Output is correct
26 Correct 1 ms 896 KB Output is correct
27 Correct 2 ms 896 KB Output is correct
28 Correct 2 ms 896 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 10968 KB Output is correct
2 Correct 43 ms 11416 KB Output is correct
3 Correct 1 ms 624 KB Output is correct
4 Correct 26 ms 10904 KB Output is correct
5 Correct 40 ms 12136 KB Output is correct
6 Correct 40 ms 12100 KB Output is correct
7 Correct 34 ms 11280 KB Output is correct
8 Correct 35 ms 11228 KB Output is correct
9 Correct 40 ms 12152 KB Output is correct
10 Correct 38 ms 12036 KB Output is correct
11 Correct 45 ms 12124 KB Output is correct
12 Correct 39 ms 12136 KB Output is correct
13 Correct 40 ms 12092 KB Output is correct
14 Correct 38 ms 12104 KB Output is correct
15 Correct 38 ms 12172 KB Output is correct
16 Correct 41 ms 12144 KB Output is correct
17 Correct 43 ms 11800 KB Output is correct
18 Correct 35 ms 11848 KB Output is correct
19 Correct 40 ms 11816 KB Output is correct
20 Correct 35 ms 11856 KB Output is correct
21 Correct 35 ms 11880 KB Output is correct
22 Correct 35 ms 11884 KB Output is correct
23 Correct 30 ms 11124 KB Output is correct
24 Correct 31 ms 11240 KB Output is correct
25 Correct 32 ms 11252 KB Output is correct
26 Correct 31 ms 11212 KB Output is correct
27 Correct 34 ms 11644 KB Output is correct
28 Correct 36 ms 11620 KB Output is correct
29 Correct 38 ms 11640 KB Output is correct
30 Correct 36 ms 11576 KB Output is correct
31 Correct 37 ms 11112 KB Output is correct
32 Correct 34 ms 11192 KB Output is correct
33 Correct 30 ms 11260 KB Output is correct
34 Correct 30 ms 11236 KB Output is correct
35 Correct 37 ms 11596 KB Output is correct
36 Correct 35 ms 11564 KB Output is correct
37 Correct 35 ms 11580 KB Output is correct
38 Correct 36 ms 11644 KB Output is correct
39 Correct 37 ms 11580 KB Output is correct
40 Correct 34 ms 11628 KB Output is correct
41 Correct 48 ms 11792 KB Output is correct
42 Correct 43 ms 11856 KB Output is correct
43 Correct 36 ms 11820 KB Output is correct
44 Correct 38 ms 11880 KB Output is correct
45 Correct 39 ms 11868 KB Output is correct
46 Correct 36 ms 11884 KB Output is correct
47 Correct 37 ms 11520 KB Output is correct
48 Correct 35 ms 11396 KB Output is correct
49 Correct 34 ms 11388 KB Output is correct
50 Correct 36 ms 11560 KB Output is correct
51 Correct 36 ms 11336 KB Output is correct
52 Correct 36 ms 11292 KB Output is correct
53 Correct 32 ms 11332 KB Output is correct
54 Correct 33 ms 11280 KB Output is correct
55 Correct 32 ms 11252 KB Output is correct
56 Correct 35 ms 11240 KB Output is correct
57 Correct 37 ms 11240 KB Output is correct
58 Correct 32 ms 11248 KB Output is correct
59 Correct 31 ms 11216 KB Output is correct
60 Correct 32 ms 11196 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11076 KB Output is correct
2 Correct 32 ms 11380 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 27 ms 10992 KB Output is correct
5 Correct 40 ms 12044 KB Output is correct
6 Correct 44 ms 12148 KB Output is correct
7 Correct 33 ms 11240 KB Output is correct
8 Correct 35 ms 11248 KB Output is correct
9 Correct 41 ms 12132 KB Output is correct
10 Correct 41 ms 12224 KB Output is correct
11 Correct 41 ms 12060 KB Output is correct
12 Correct 45 ms 12112 KB Output is correct
13 Correct 41 ms 12108 KB Output is correct
14 Correct 39 ms 12152 KB Output is correct
15 Correct 38 ms 12096 KB Output is correct
16 Correct 42 ms 12196 KB Output is correct
17 Correct 40 ms 11788 KB Output is correct
18 Correct 35 ms 11836 KB Output is correct
19 Correct 35 ms 11836 KB Output is correct
20 Correct 35 ms 11880 KB Output is correct
21 Correct 38 ms 11816 KB Output is correct
22 Correct 38 ms 11768 KB Output is correct
23 Correct 32 ms 11080 KB Output is correct
24 Correct 31 ms 11228 KB Output is correct
25 Correct 34 ms 11252 KB Output is correct
26 Correct 33 ms 11152 KB Output is correct
27 Correct 38 ms 11584 KB Output is correct
28 Correct 36 ms 11576 KB Output is correct
29 Correct 35 ms 11604 KB Output is correct
30 Correct 36 ms 11676 KB Output is correct
31 Correct 35 ms 11100 KB Output is correct
32 Correct 34 ms 11212 KB Output is correct
33 Correct 34 ms 11204 KB Output is correct
34 Correct 32 ms 11164 KB Output is correct
35 Correct 36 ms 11484 KB Output is correct
36 Correct 43 ms 11696 KB Output is correct
37 Correct 49 ms 11552 KB Output is correct
38 Correct 35 ms 11524 KB Output is correct
39 Correct 36 ms 11608 KB Output is correct
40 Correct 39 ms 11540 KB Output is correct
41 Correct 41 ms 11924 KB Output is correct
42 Correct 38 ms 11796 KB Output is correct
43 Correct 40 ms 11732 KB Output is correct
44 Correct 40 ms 11896 KB Output is correct
45 Correct 37 ms 11872 KB Output is correct
46 Correct 38 ms 11796 KB Output is correct
47 Correct 40 ms 11468 KB Output is correct
48 Correct 33 ms 11484 KB Output is correct
49 Correct 39 ms 11364 KB Output is correct
50 Correct 37 ms 11568 KB Output is correct
51 Correct 34 ms 11284 KB Output is correct
52 Correct 31 ms 11336 KB Output is correct
53 Correct 31 ms 11296 KB Output is correct
54 Correct 31 ms 11360 KB Output is correct
55 Correct 33 ms 11356 KB Output is correct
56 Correct 38 ms 11316 KB Output is correct
57 Correct 32 ms 11248 KB Output is correct
58 Correct 31 ms 11248 KB Output is correct
59 Correct 33 ms 11236 KB Output is correct
60 Correct 32 ms 11240 KB Output is correct