oj.uz

Submission #748680

# Submission time Handle Problem Language Result Execution time Memory
748680 2023-05-26T17:52:21 Z piOOE Stray Cat (JOI20_stray) C++17
20 / 100
 60 ms 16680 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, 1, 0, 0, 1};
        vector<int> dp(N, -1);

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

            if (x && adj[x].size() > 2) {
                int c = e[x] == -1 || X[e[x]] == 1 ? 0 : 1;
                for (auto [to, i] : adj[x]) {
                    if (i != e[x]) {
                        X[i] = c;
                    }
                }
            } else {
                dp[x] = (dp[x] + 1) % size(code);

                for (auto [to, i] : adj[x]) {
                    if (i != e[x]) {
                        X[i] = code[dp[x]];
                        dp[to] = dp[x];
                    }
                }
            }
        }
    }

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

    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, 1, 0, 0, 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 (A >= 3) {
        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

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:48:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |             if (e[x] == -1 || par[x] && adj[par[x]].size() >= 3) {

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 40 ms 15472 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 32 ms 14872 KB Output is correct
4 Correct 52 ms 16680 KB Output is correct
5 Correct 60 ms 16388 KB Output is correct
6 Correct 43 ms 15152 KB Output is correct
7 Correct 37 ms 15192 KB Output is correct
8 Correct 41 ms 15892 KB Output is correct
9 Correct 47 ms 15968 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15472 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 32 ms 14872 KB Output is correct
4 Correct 52 ms 16680 KB Output is correct
5 Correct 60 ms 16388 KB Output is correct
6 Correct 43 ms 15152 KB Output is correct
7 Correct 37 ms 15192 KB Output is correct
8 Correct 41 ms 15892 KB Output is correct
9 Correct 47 ms 15968 KB Output is correct
10 Correct 40 ms 13264 KB Output is correct
11 Correct 37 ms 13252 KB Output is correct
12 Correct 35 ms 13252 KB Output is correct
13 Correct 35 ms 13252 KB Output is correct
14 Correct 36 ms 13480 KB Output is correct
15 Correct 41 ms 13868 KB Output is correct
16 Correct 44 ms 15972 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13016 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 30 ms 12668 KB Output is correct
4 Correct 46 ms 14248 KB Output is correct
5 Correct 51 ms 14208 KB Output is correct
6 Correct 38 ms 12952 KB Output is correct
7 Correct 37 ms 12956 KB Output is correct
8 Correct 39 ms 13668 KB Output is correct
9 Correct 39 ms 13668 KB Output is correct
10 Correct 39 ms 13424 KB Output is correct
11 Correct 38 ms 13448 KB Output is correct
12 Correct 39 ms 13440 KB Output is correct
13 Correct 51 ms 13304 KB Output is correct
14 Correct 44 ms 13660 KB Output is correct
15 Correct 41 ms 13644 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 13016 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 30 ms 12668 KB Output is correct
4 Correct 46 ms 14248 KB Output is correct
5 Correct 51 ms 14208 KB Output is correct
6 Correct 38 ms 12952 KB Output is correct
7 Correct 37 ms 12956 KB Output is correct
8 Correct 39 ms 13668 KB Output is correct
9 Correct 39 ms 13668 KB Output is correct
10 Correct 39 ms 13424 KB Output is correct
11 Correct 38 ms 13448 KB Output is correct
12 Correct 39 ms 13440 KB Output is correct
13 Correct 51 ms 13304 KB Output is correct
14 Correct 44 ms 13660 KB Output is correct
15 Correct 41 ms 13644 KB Output is correct
16 Correct 34 ms 11356 KB Output is correct
17 Correct 33 ms 11212 KB Output is correct
18 Correct 41 ms 11360 KB Output is correct
19 Correct 36 ms 11332 KB Output is correct
20 Correct 39 ms 11928 KB Output is correct
21 Correct 34 ms 11776 KB Output is correct
22 Correct 44 ms 13800 KB Output is correct
23 Correct 38 ms 11496 KB Output is correct
24 Correct 36 ms 11468 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11168 KB Output is correct
2 Correct 40 ms 11428 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 28 ms 11052 KB Output is correct
5 Correct 52 ms 12264 KB Output is correct
6 Correct 41 ms 12236 KB Output is correct
7 Incorrect 32 ms 11348 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11200 KB Output is correct
2 Correct 34 ms 11316 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 26 ms 11032 KB Output is correct
5 Correct 41 ms 12208 KB Output is correct
6 Correct 46 ms 12296 KB Output is correct
7 Incorrect 34 ms 11352 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -