oj.uz

Submission #748655

# Submission time Handle Problem Language Result Execution time Memory
748655 2023-05-26T17:07:45 Z piOOE Stray Cat (JOI20_stray) C++17
20 / 100
 48 ms 16520 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]] != code[0] ? code[0] : code[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 38 ms 15396 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 31 ms 14856 KB Output is correct
4 Correct 48 ms 16384 KB Output is correct
5 Correct 47 ms 16520 KB Output is correct
6 Correct 36 ms 15216 KB Output is correct
7 Correct 39 ms 15248 KB Output is correct
8 Correct 41 ms 15916 KB Output is correct
9 Correct 41 ms 15888 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15396 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 31 ms 14856 KB Output is correct
4 Correct 48 ms 16384 KB Output is correct
5 Correct 47 ms 16520 KB Output is correct
6 Correct 36 ms 15216 KB Output is correct
7 Correct 39 ms 15248 KB Output is correct
8 Correct 41 ms 15916 KB Output is correct
9 Correct 41 ms 15888 KB Output is correct
10 Correct 33 ms 13124 KB Output is correct
11 Correct 34 ms 13284 KB Output is correct
12 Correct 31 ms 13284 KB Output is correct
13 Correct 32 ms 13292 KB Output is correct
14 Correct 34 ms 13524 KB Output is correct
15 Correct 40 ms 13828 KB Output is correct
16 Correct 41 ms 15932 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13004 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 12568 KB Output is correct
4 Correct 43 ms 14300 KB Output is correct
5 Correct 43 ms 14208 KB Output is correct
6 Correct 34 ms 12908 KB Output is correct
7 Correct 34 ms 12908 KB Output is correct
8 Correct 37 ms 13596 KB Output is correct
9 Correct 40 ms 13768 KB Output is correct
10 Correct 38 ms 13364 KB Output is correct
11 Correct 36 ms 13412 KB Output is correct
12 Correct 37 ms 13384 KB Output is correct
13 Correct 37 ms 13404 KB Output is correct
14 Correct 41 ms 13744 KB Output is correct
15 Correct 46 ms 13780 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13004 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 12568 KB Output is correct
4 Correct 43 ms 14300 KB Output is correct
5 Correct 43 ms 14208 KB Output is correct
6 Correct 34 ms 12908 KB Output is correct
7 Correct 34 ms 12908 KB Output is correct
8 Correct 37 ms 13596 KB Output is correct
9 Correct 40 ms 13768 KB Output is correct
10 Correct 38 ms 13364 KB Output is correct
11 Correct 36 ms 13412 KB Output is correct
12 Correct 37 ms 13384 KB Output is correct
13 Correct 37 ms 13404 KB Output is correct
14 Correct 41 ms 13744 KB Output is correct
15 Correct 46 ms 13780 KB Output is correct
16 Correct 31 ms 11308 KB Output is correct
17 Correct 31 ms 11500 KB Output is correct
18 Correct 32 ms 11348 KB Output is correct
19 Correct 31 ms 11304 KB Output is correct
20 Correct 40 ms 11992 KB Output is correct
21 Correct 34 ms 11728 KB Output is correct
22 Correct 40 ms 13900 KB Output is correct
23 Correct 34 ms 11432 KB Output is correct
24 Correct 31 ms 11500 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 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 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 896 KB Output is correct
9 Correct 2 ms 904 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 2 ms 904 KB Output is correct
13 Correct 2 ms 892 KB Output is correct
14 Correct 2 ms 904 KB Output is correct
15 Correct 1 ms 904 KB Output is correct
16 Correct 2 ms 896 KB Output is correct
17 Correct 2 ms 900 KB Output is correct
18 Correct 2 ms 904 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 2 ms 896 KB Output is correct
22 Correct 2 ms 904 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 1020 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 31 ms 11092 KB Output is correct
2 Correct 36 ms 11544 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 28 ms 11116 KB Output is correct
5 Correct 41 ms 12212 KB Output is correct
6 Correct 41 ms 12244 KB Output is correct
7 Incorrect 33 ms 11380 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11308 KB Output is correct
2 Correct 36 ms 11504 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 28 ms 11112 KB Output is correct
5 Correct 42 ms 12240 KB Output is correct
6 Correct 40 ms 12220 KB Output is correct
7 Incorrect 30 ms 11368 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -