oj.uz

Submission #782960

# Submission time Handle Problem Language Result Execution time Memory
782960 2023-07-14T12:54:46 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 65 ms 19004 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 pathAmount(vector<int> y) {
        int sum = 1;
        for (int el : y) sum += el;
        return sum;
    }

} // 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 (::pathAmount(y) != 3) {
                    ::prevA = (y[0] == 1 ? 0 : 1);
                    ::onPath = true;
                    return (y[0] == 1 ? 0 : 1);
                }
                return 0;
            }
            if (::pathAmount(y) > 2) {
                ::prevA = (y[0] == 1 ? 0 : (y[1] == 1 ? 1 : ::prevA));
                ::onPath = true;
                return (y[0] == 1 ? 0 : (y[1] == 1 ? 1 : -1));
            } else if (::pathAmount(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:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         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 43 ms 17632 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 38 ms 17528 KB Output is correct
4 Correct 56 ms 19004 KB Output is correct
5 Correct 65 ms 18988 KB Output is correct
6 Correct 41 ms 17816 KB Output is correct
7 Correct 47 ms 18140 KB Output is correct
8 Correct 46 ms 18620 KB Output is correct
9 Correct 50 ms 18644 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17632 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 38 ms 17528 KB Output is correct
4 Correct 56 ms 19004 KB Output is correct
5 Correct 65 ms 18988 KB Output is correct
6 Correct 41 ms 17816 KB Output is correct
7 Correct 47 ms 18140 KB Output is correct
8 Correct 46 ms 18620 KB Output is correct
9 Correct 50 ms 18644 KB Output is correct
10 Correct 40 ms 15972 KB Output is correct
11 Correct 41 ms 15884 KB Output is correct
12 Correct 41 ms 15924 KB Output is correct
13 Correct 41 ms 15896 KB Output is correct
14 Correct 46 ms 16164 KB Output is correct
15 Correct 41 ms 16568 KB Output is correct
16 Correct 46 ms 18656 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15264 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 36 ms 15040 KB Output is correct
4 Correct 46 ms 16596 KB Output is correct
5 Correct 45 ms 16536 KB Output is correct
6 Correct 41 ms 15196 KB Output is correct
7 Correct 41 ms 15200 KB Output is correct
8 Correct 45 ms 15852 KB Output is correct
9 Correct 44 ms 15812 KB Output is correct
10 Correct 43 ms 15568 KB Output is correct
11 Correct 43 ms 15584 KB Output is correct
12 Correct 44 ms 15576 KB Output is correct
13 Correct 41 ms 15644 KB Output is correct
14 Correct 49 ms 15896 KB Output is correct
15 Correct 55 ms 15864 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15264 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 36 ms 15040 KB Output is correct
4 Correct 46 ms 16596 KB Output is correct
5 Correct 45 ms 16536 KB Output is correct
6 Correct 41 ms 15196 KB Output is correct
7 Correct 41 ms 15200 KB Output is correct
8 Correct 45 ms 15852 KB Output is correct
9 Correct 44 ms 15812 KB Output is correct
10 Correct 43 ms 15568 KB Output is correct
11 Correct 43 ms 15584 KB Output is correct
12 Correct 44 ms 15576 KB Output is correct
13 Correct 41 ms 15644 KB Output is correct
14 Correct 49 ms 15896 KB Output is correct
15 Correct 55 ms 15864 KB Output is correct
16 Correct 38 ms 13804 KB Output is correct
17 Correct 37 ms 13788 KB Output is correct
18 Correct 44 ms 13508 KB Output is correct
19 Correct 39 ms 13644 KB Output is correct
20 Correct 40 ms 14184 KB Output is correct
21 Correct 41 ms 14000 KB Output is correct
22 Correct 43 ms 15980 KB Output is correct
23 Correct 40 ms 13664 KB Output is correct
24 Correct 39 ms 13732 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 508 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 908 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 964 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 900 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 904 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 896 KB Output is correct
16 Incorrect 2 ms 896 KB Wrong Answer [5]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 13516 KB Output is correct
2 Correct 42 ms 14040 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 38 ms 13596 KB Output is correct
5 Correct 48 ms 14916 KB Output is correct
6 Correct 44 ms 14880 KB Output is correct
7 Incorrect 37 ms 14204 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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