oj.uz

Submission #747828

# Submission time Handle Problem Language Result Execution time Memory
747828 2023-05-24T21:07:12 Z piOOE Stray Cat (JOI20_stray) C++17
20 / 100
 49 ms 16492 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 (B == 0) {
        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 {
        for (int i = 1; i < N; ++i) {
            if (adj[i].size() > 2) {
                for (auto [to, j] : adj[i]) {
                    X[j] = (dist[i] % 2) ^ (e[i] != j);
                }
            }
        }

        vector<int> code{0, 1, 0, 0, 1, 1};
        vector<int> dp(N, -1);

        reverse(ord.begin(), ord.end());

        for (int x : ord) {
            if (e[x] == -1 || X[e[x]] != -1) {
                continue;
            }
            dp[x] = (dp[x] + 1) % size(code);
            X[e[x]] = code[dp[x]];
            dp[par[x]] = dp[x];
        }
    }

    return X;
}

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

using namespace std;

namespace {
    int A, B, e = -1;
    bool ok = false;

    vector<int> adj;
    vector<int> code{0, 1, 0, 0, 1, 1};

    bool extendable(vector<int> a) {
        for (int i = 0; i < size(code); ++i) {
            bool yay = true;

            for (int k = 0; k < size(a); ++k) {
                if (a[k] != code[(i + k) % size(code)]) {
                    yay = false;
                    break;
                }
            }

            if (yay) {
                return true;
            }
        }

        return false;
    }
}

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

int Move(std::vector<int> y) {
    if (e != -1) {
        y[e] += 1;
    }

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

    if (B == 0) {
        int fi = -1, se = -1, cnt = 0;

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

        if (fi != 0 || se != 2) {
            return e = fi;
        } else {
            return e = se;
        }
    } else {
        if (size(adj) >= size(code)) {
            ok = true;
        }
        if (deg > 2) {
            ok = true;
            for (int i = 0; i < A; ++i) {
                if (y[i] == 1) {
                    if (i == e) {
                        return -1;
                    } else {
                        return e = i;
                    }
                }
            }
        } else if (deg == 1) {
            ok = true;
            for (int i = 0; i < A; ++i) {
                if (y[i]) {
                    if (i == e) {
                        return -1;
                    } else {
                        return e = i;
                    }
                }
            }
        } else if (ok) {
            --y[e];
            for (int i = 0; i < A; ++i) {
                if (y[i]) {
                    return e = i;
                }
            }
        }  else {
            int a = -1, b = -1;

            for (int i = 0; i < A; ++i) {
                if (y[i]) {
                    a = a == -1 ? i : a;
                    b = i;
                }
            }

            if (e == -1) {
                adj.push_back(a);
                adj.push_back(b);
                return e = b;
            }

            int c = a ^ b ^ e;
            adj.push_back(c);

            if (extendable(adj)) {
                return e = c;
            } else {
                ok = true;
                return -1;
            }
        }

        assert(false);
    }
}

Compilation message

Catherine.cpp: In function 'bool {anonymous}::extendable(std::vector<int>)':
Catherine.cpp:14:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for (int i = 0; i < size(code); ++i) {
      |                         ~~^~~~~~~~~~~~
Catherine.cpp:17:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |             for (int k = 0; k < size(a); ++k) {
      |                             ~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15436 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 30 ms 14804 KB Output is correct
4 Correct 49 ms 16368 KB Output is correct
5 Correct 48 ms 16492 KB Output is correct
6 Correct 41 ms 15240 KB Output is correct
7 Correct 35 ms 15216 KB Output is correct
8 Correct 41 ms 15908 KB Output is correct
9 Correct 42 ms 16012 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15436 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 30 ms 14804 KB Output is correct
4 Correct 49 ms 16368 KB Output is correct
5 Correct 48 ms 16492 KB Output is correct
6 Correct 41 ms 15240 KB Output is correct
7 Correct 35 ms 15216 KB Output is correct
8 Correct 41 ms 15908 KB Output is correct
9 Correct 42 ms 16012 KB Output is correct
10 Correct 32 ms 13164 KB Output is correct
11 Correct 33 ms 13236 KB Output is correct
12 Correct 33 ms 13232 KB Output is correct
13 Correct 32 ms 13224 KB Output is correct
14 Correct 33 ms 13552 KB Output is correct
15 Correct 38 ms 13940 KB Output is correct
16 Correct 40 ms 15976 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12952 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 28 ms 12664 KB Output is correct
4 Correct 43 ms 14244 KB Output is correct
5 Correct 44 ms 14272 KB Output is correct
6 Correct 33 ms 13000 KB Output is correct
7 Correct 35 ms 12944 KB Output is correct
8 Correct 41 ms 13684 KB Output is correct
9 Correct 41 ms 13604 KB Output is correct
10 Correct 39 ms 13392 KB Output is correct
11 Correct 39 ms 13532 KB Output is correct
12 Correct 37 ms 13400 KB Output is correct
13 Correct 39 ms 13344 KB Output is correct
14 Correct 40 ms 13628 KB Output is correct
15 Correct 39 ms 13796 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12952 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 28 ms 12664 KB Output is correct
4 Correct 43 ms 14244 KB Output is correct
5 Correct 44 ms 14272 KB Output is correct
6 Correct 33 ms 13000 KB Output is correct
7 Correct 35 ms 12944 KB Output is correct
8 Correct 41 ms 13684 KB Output is correct
9 Correct 41 ms 13604 KB Output is correct
10 Correct 39 ms 13392 KB Output is correct
11 Correct 39 ms 13532 KB Output is correct
12 Correct 37 ms 13400 KB Output is correct
13 Correct 39 ms 13344 KB Output is correct
14 Correct 40 ms 13628 KB Output is correct
15 Correct 39 ms 13796 KB Output is correct
16 Correct 30 ms 11424 KB Output is correct
17 Correct 30 ms 11360 KB Output is correct
18 Correct 31 ms 11312 KB Output is correct
19 Correct 31 ms 11312 KB Output is correct
20 Correct 35 ms 12076 KB Output is correct
21 Correct 32 ms 11744 KB Output is correct
22 Correct 38 ms 13820 KB Output is correct
23 Correct 37 ms 11508 KB Output is correct
24 Correct 32 ms 11468 KB Output is correct

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 460 KB Output is correct
3 Correct 2 ms 908 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 896 KB Output is correct
7 Correct 2 ms 904 KB Output is correct
8 Correct 2 ms 872 KB Output is correct
9 Correct 2 ms 872 KB Output is correct
10 Correct 2 ms 908 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 908 KB Output is correct
14 Correct 2 ms 836 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 2 ms 908 KB Output is correct
19 Correct 2 ms 908 KB Output is correct
20 Correct 2 ms 908 KB Output is correct
21 Correct 2 ms 908 KB Output is correct
22 Correct 2 ms 908 KB Output is correct
23 Correct 2 ms 904 KB Output is correct
24 Correct 2 ms 908 KB Output is correct
25 Correct 2 ms 900 KB Output is correct
26 Correct 2 ms 908 KB Output is correct
27 Correct 2 ms 908 KB Output is correct
28 Correct 2 ms 900 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11252 KB Output is correct
2 Correct 34 ms 11612 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 27 ms 11032 KB Output is correct
5 Correct 39 ms 12336 KB Output is correct
6 Correct 41 ms 12184 KB Output is correct
7 Correct 33 ms 11364 KB Output is correct
8 Correct 33 ms 11816 KB Output is correct
9 Correct 44 ms 12600 KB Output is correct
10 Correct 44 ms 12648 KB Output is correct
11 Correct 40 ms 12696 KB Output is correct
12 Correct 41 ms 12632 KB Output is correct
13 Correct 39 ms 12712 KB Output is correct
14 Correct 38 ms 12676 KB Output is correct
15 Correct 42 ms 12920 KB Output is correct
16 Correct 46 ms 12668 KB Output is correct
17 Correct 41 ms 12404 KB Output is correct
18 Correct 38 ms 12400 KB Output is correct
19 Correct 38 ms 12364 KB Output is correct
20 Correct 37 ms 12400 KB Output is correct
21 Correct 36 ms 12392 KB Output is correct
22 Correct 37 ms 12400 KB Output is correct
23 Incorrect 31 ms 11532 KB Wrong Answer [6]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11120 KB Output is correct
2 Correct 33 ms 11484 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 27 ms 11116 KB Output is correct
5 Correct 40 ms 12284 KB Output is correct
6 Correct 43 ms 12380 KB Output is correct
7 Correct 32 ms 11388 KB Output is correct
8 Correct 35 ms 11828 KB Output is correct
9 Correct 43 ms 12596 KB Output is correct
10 Correct 40 ms 12716 KB Output is correct
11 Correct 39 ms 12728 KB Output is correct
12 Correct 40 ms 12776 KB Output is correct
13 Correct 43 ms 12684 KB Output is correct
14 Correct 40 ms 12696 KB Output is correct
15 Correct 38 ms 12748 KB Output is correct
16 Correct 38 ms 12656 KB Output is correct
17 Correct 36 ms 12404 KB Output is correct
18 Correct 35 ms 12376 KB Output is correct
19 Correct 41 ms 12480 KB Output is correct
20 Correct 37 ms 12348 KB Output is correct
21 Correct 37 ms 12472 KB Output is correct
22 Correct 38 ms 12344 KB Output is correct
23 Correct 31 ms 11572 KB Output is correct
24 Correct 31 ms 11528 KB Output is correct
25 Correct 33 ms 11812 KB Output is correct
26 Correct 36 ms 11748 KB Output is correct
27 Correct 35 ms 12160 KB Output is correct
28 Correct 37 ms 12180 KB Output is correct
29 Correct 37 ms 12112 KB Output is correct
30 Correct 38 ms 12224 KB Output is correct
31 Correct 31 ms 11580 KB Output is correct
32 Correct 32 ms 11664 KB Output is correct
33 Correct 34 ms 11840 KB Output is correct
34 Correct 32 ms 11792 KB Output is correct
35 Correct 34 ms 12020 KB Output is correct
36 Correct 36 ms 11984 KB Output is correct
37 Correct 36 ms 12044 KB Output is correct
38 Incorrect 34 ms 12020 KB Wrong Answer [6]
39 Halted 0 ms 0 KB -