Submission #783022

# Submission time Handle Problem Language Result Execution time Memory
783022 2023-07-14T14:21:03 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
62 ms 18784 KB
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;


std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V)
{
    vector<vector<ii>> ADJ(N);
    map<ii, int> paths;
    vector<bool> filled(M, false);
    for (int i = 0; i < M; i++) {
        ADJ[U[i]].push_back({V[i], i});
        ADJ[V[i]].push_back({U[i], i});
        paths[{U[i], V[i]}] = i;
        paths[{V[i], U[i]}] = i;
    }

    std::vector<int> X(M);
    priority_queue<ii, vector<ii>, greater<ii>> q;
    vector<int> prevNode(N, -1);
    vector<int> shortest(N, 1e8);
    shortest[0] = 0;
    q.push({0,0});
    while (!q.empty()) {
        auto [dis, pos] = q.top();
        q.pop();
        if (dis != shortest[pos]) continue;
        for (auto [conn, _] : ADJ[pos]) {
            if (dis+1 < shortest[conn]) {
                shortest[conn] = dis+1;
                prevNode[conn] = pos;
                q.push({dis+1, conn});
            }
        }
    }
    for (int p = 1; p < N; p++) {
        X[paths[{p, prevNode[p]}]] = shortest[p]%(A==2?2:3);
        filled[paths[{p, prevNode[p]}]] = true;
    }
    for (int i = 0; i < M; i++) if (!filled[i]) {
        X[i] = (min(shortest[U[i]], shortest[V[i]])+1)%(A==2?2:3);
    }
    return X;
    
}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

namespace
{

    int A, B;
    int prevA = 0;
    bool onPath = false;
    bool first = true;

} // namespace

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

int Move(std::vector<int> y)
{
    if (A==2) {
        if (!::onPath) {
            if (::first) {
                ::first = false;
                if (y[0]+y[1] != 2) {
                    ::prevA = (y[0] == 1 ? 0 : 1);
                    ::onPath = true;
                    return (y[0] == 1 ? 0 : 1);
                }
                return 0;
            }
            if (y[0] + y[1] > 1) {
                ::prevA = (y[0] == 1 ? 0 : (y[1] == 1 ? 1 : ::prevA));
                ::onPath = true;
                return (y[0] == 1 ? 0 : (y[1] == 1 ? 1 : -1));
            } else if (!y[0] && !y[1]) {
                ::onPath = true;
                return -1;
            } else {
                ::prevA = !::prevA;
                return ::prevA;
            }
        } else {
            ::prevA = !::prevA;
            return ::prevA;
        }
    } else {
        first = false;
        int corr = -1;
        for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
        return corr;
    }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:54:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
      |                          ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 46 ms 17560 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 50 ms 17112 KB Output is correct
4 Correct 58 ms 18684 KB Output is correct
5 Correct 53 ms 18784 KB Output is correct
6 Correct 49 ms 17432 KB Output is correct
7 Correct 49 ms 17472 KB Output is correct
8 Correct 58 ms 18044 KB Output is correct
9 Correct 50 ms 18124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 46 ms 17560 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 50 ms 17112 KB Output is correct
4 Correct 58 ms 18684 KB Output is correct
5 Correct 53 ms 18784 KB Output is correct
6 Correct 49 ms 17432 KB Output is correct
7 Correct 49 ms 17472 KB Output is correct
8 Correct 58 ms 18044 KB Output is correct
9 Correct 50 ms 18124 KB Output is correct
10 Correct 46 ms 15484 KB Output is correct
11 Correct 41 ms 15560 KB Output is correct
12 Correct 44 ms 15372 KB Output is correct
13 Correct 48 ms 15488 KB Output is correct
14 Correct 45 ms 15644 KB Output is correct
15 Correct 62 ms 16036 KB Output is correct
16 Correct 52 ms 18180 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 44 ms 15332 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 40 ms 15044 KB Output is correct
4 Correct 50 ms 16492 KB Output is correct
5 Correct 51 ms 16484 KB Output is correct
6 Correct 45 ms 15364 KB Output is correct
7 Correct 43 ms 15328 KB Output is correct
8 Correct 45 ms 15852 KB Output is correct
9 Correct 51 ms 15804 KB Output is correct
10 Correct 43 ms 15576 KB Output is correct
11 Correct 48 ms 15652 KB Output is correct
12 Correct 44 ms 15560 KB Output is correct
13 Correct 44 ms 15652 KB Output is correct
14 Correct 57 ms 15892 KB Output is correct
15 Correct 45 ms 15920 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 44 ms 15332 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 40 ms 15044 KB Output is correct
4 Correct 50 ms 16492 KB Output is correct
5 Correct 51 ms 16484 KB Output is correct
6 Correct 45 ms 15364 KB Output is correct
7 Correct 43 ms 15328 KB Output is correct
8 Correct 45 ms 15852 KB Output is correct
9 Correct 51 ms 15804 KB Output is correct
10 Correct 43 ms 15576 KB Output is correct
11 Correct 48 ms 15652 KB Output is correct
12 Correct 44 ms 15560 KB Output is correct
13 Correct 44 ms 15652 KB Output is correct
14 Correct 57 ms 15892 KB Output is correct
15 Correct 45 ms 15920 KB Output is correct
16 Correct 41 ms 13716 KB Output is correct
17 Correct 40 ms 13824 KB Output is correct
18 Correct 39 ms 13616 KB Output is correct
19 Correct 40 ms 13576 KB Output is correct
20 Correct 48 ms 14156 KB Output is correct
21 Correct 40 ms 13956 KB Output is correct
22 Correct 43 ms 16112 KB Output is correct
23 Correct 40 ms 13700 KB Output is correct
24 Correct 40 ms 13708 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 2 ms 900 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 900 KB Output is correct
8 Correct 2 ms 908 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 892 KB Output is correct
12 Correct 2 ms 896 KB Output is correct
13 Correct 2 ms 928 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 2 ms 904 KB Output is correct
16 Incorrect 2 ms 904 KB Wrong Answer [5]
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 40 ms 13552 KB Output is correct
2 Correct 46 ms 13940 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 39 ms 13648 KB Output is correct
5 Correct 45 ms 14928 KB Output is correct
6 Correct 52 ms 14856 KB Output is correct
7 Incorrect 41 ms 14080 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 41 ms 13488 KB Output is correct
2 Incorrect 38 ms 13548 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -