oj.uz

Submission #786636

# Submission time Handle Problem Language Result Execution time Memory
786636 2023-07-18T10:35:13 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 55 ms 18720 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;

    int findNext2(vector<int> y) {
        if (!::onPath) {
            if (::first) {
                ::first = false;
                if (y[0]+y[1] != 2) {
                    ::onPath = true;
                    return (y[0] == 1 ? 0 : 1);
                }
                return 0;
            }
            if (y[0] + y[1] > 1) {
                ::onPath = true;
                return (y[0] == 1 ? 0 : (y[1] == 1 ? 1 : -1));
            } else if (y[0] + y[1] == 0) {
                ::onPath = true;
                return -1;
            } else {
                return !::prevA;
            }
        } else {
            return !::prevA;
        }
    }

} 

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

int Move(std::vector<int> y)
{
    if (A==2) {
        int res = findNext2(y);
        if (res != -1) ::prevA = res;
        return res;
    } 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:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
      |                          ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17632 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 39 ms 17180 KB Output is correct
4 Correct 47 ms 18720 KB Output is correct
5 Correct 50 ms 18696 KB Output is correct
6 Correct 41 ms 17472 KB Output is correct
7 Correct 43 ms 17428 KB Output is correct
8 Correct 55 ms 18228 KB Output is correct
9 Correct 47 ms 18132 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17632 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 39 ms 17180 KB Output is correct
4 Correct 47 ms 18720 KB Output is correct
5 Correct 50 ms 18696 KB Output is correct
6 Correct 41 ms 17472 KB Output is correct
7 Correct 43 ms 17428 KB Output is correct
8 Correct 55 ms 18228 KB Output is correct
9 Correct 47 ms 18132 KB Output is correct
10 Correct 41 ms 15436 KB Output is correct
11 Correct 44 ms 15512 KB Output is correct
12 Correct 39 ms 15488 KB Output is correct
13 Correct 39 ms 15584 KB Output is correct
14 Correct 40 ms 15712 KB Output is correct
15 Correct 47 ms 16180 KB Output is correct
16 Correct 49 ms 18236 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15276 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 34 ms 15092 KB Output is correct
4 Correct 46 ms 16552 KB Output is correct
5 Correct 54 ms 16492 KB Output is correct
6 Correct 49 ms 15420 KB Output is correct
7 Correct 47 ms 15428 KB Output is correct
8 Correct 47 ms 15924 KB Output is correct
9 Correct 48 ms 15776 KB Output is correct
10 Correct 43 ms 15620 KB Output is correct
11 Correct 41 ms 15700 KB Output is correct
12 Correct 41 ms 15500 KB Output is correct
13 Correct 50 ms 15676 KB Output is correct
14 Correct 43 ms 15956 KB Output is correct
15 Correct 43 ms 15836 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15276 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 34 ms 15092 KB Output is correct
4 Correct 46 ms 16552 KB Output is correct
5 Correct 54 ms 16492 KB Output is correct
6 Correct 49 ms 15420 KB Output is correct
7 Correct 47 ms 15428 KB Output is correct
8 Correct 47 ms 15924 KB Output is correct
9 Correct 48 ms 15776 KB Output is correct
10 Correct 43 ms 15620 KB Output is correct
11 Correct 41 ms 15700 KB Output is correct
12 Correct 41 ms 15500 KB Output is correct
13 Correct 50 ms 15676 KB Output is correct
14 Correct 43 ms 15956 KB Output is correct
15 Correct 43 ms 15836 KB Output is correct
16 Correct 38 ms 13768 KB Output is correct
17 Correct 40 ms 13812 KB Output is correct
18 Correct 39 ms 13684 KB Output is correct
19 Correct 39 ms 13616 KB Output is correct
20 Correct 40 ms 14204 KB Output is correct
21 Correct 44 ms 13992 KB Output is correct
22 Correct 44 ms 16024 KB Output is correct
23 Correct 39 ms 13648 KB Output is correct
24 Correct 39 ms 13612 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 892 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 1 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 896 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 892 KB Output is correct
11 Correct 2 ms 904 KB Output is correct
12 Correct 2 ms 900 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 Incorrect 2 ms 904 KB Wrong Answer [5]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13532 KB Output is correct
2 Correct 44 ms 13920 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 37 ms 13992 KB Output is correct
5 Correct 47 ms 15164 KB Output is correct
6 Correct 46 ms 15128 KB Output is correct
7 Incorrect 41 ms 14356 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13444 KB Output is correct
2 Incorrect 38 ms 13660 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -