oj.uz

Submission #783012

# Submission time Handle Problem Language Result Execution time Memory
783012 2023-07-14T14:15:02 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 53 ms 18968 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]) {
                ::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;
      |                          ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18080 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 41 ms 17416 KB Output is correct
4 Correct 49 ms 18968 KB Output is correct
5 Correct 49 ms 18964 KB Output is correct
6 Correct 44 ms 17760 KB Output is correct
7 Correct 43 ms 17748 KB Output is correct
8 Correct 47 ms 18388 KB Output is correct
9 Correct 47 ms 18452 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18080 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 41 ms 17416 KB Output is correct
4 Correct 49 ms 18968 KB Output is correct
5 Correct 49 ms 18964 KB Output is correct
6 Correct 44 ms 17760 KB Output is correct
7 Correct 43 ms 17748 KB Output is correct
8 Correct 47 ms 18388 KB Output is correct
9 Correct 47 ms 18452 KB Output is correct
10 Correct 42 ms 15676 KB Output is correct
11 Correct 44 ms 15856 KB Output is correct
12 Correct 40 ms 15760 KB Output is correct
13 Correct 40 ms 15624 KB Output is correct
14 Correct 41 ms 16036 KB Output is correct
15 Correct 44 ms 16452 KB Output is correct
16 Correct 47 ms 18524 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15672 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 37 ms 15404 KB Output is correct
4 Correct 46 ms 17064 KB Output is correct
5 Correct 53 ms 16920 KB Output is correct
6 Correct 42 ms 15680 KB Output is correct
7 Correct 48 ms 15752 KB Output is correct
8 Correct 45 ms 16236 KB Output is correct
9 Correct 46 ms 16264 KB Output is correct
10 Correct 49 ms 16024 KB Output is correct
11 Correct 45 ms 15964 KB Output is correct
12 Correct 43 ms 16112 KB Output is correct
13 Correct 46 ms 16108 KB Output is correct
14 Correct 48 ms 16340 KB Output is correct
15 Correct 46 ms 16268 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15672 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 37 ms 15404 KB Output is correct
4 Correct 46 ms 17064 KB Output is correct
5 Correct 53 ms 16920 KB Output is correct
6 Correct 42 ms 15680 KB Output is correct
7 Correct 48 ms 15752 KB Output is correct
8 Correct 45 ms 16236 KB Output is correct
9 Correct 46 ms 16264 KB Output is correct
10 Correct 49 ms 16024 KB Output is correct
11 Correct 45 ms 15964 KB Output is correct
12 Correct 43 ms 16112 KB Output is correct
13 Correct 46 ms 16108 KB Output is correct
14 Correct 48 ms 16340 KB Output is correct
15 Correct 46 ms 16268 KB Output is correct
16 Correct 38 ms 14272 KB Output is correct
17 Correct 39 ms 14256 KB Output is correct
18 Correct 39 ms 14004 KB Output is correct
19 Correct 39 ms 13932 KB Output is correct
20 Correct 45 ms 14620 KB Output is correct
21 Correct 42 ms 14408 KB Output is correct
22 Correct 41 ms 16428 KB Output is correct
23 Correct 40 ms 14160 KB Output is correct
24 Correct 40 ms 14040 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 908 KB Output is correct
6 Correct 2 ms 908 KB Output is correct
7 Correct 3 ms 984 KB Output is correct
8 Correct 2 ms 908 KB Output is correct
9 Correct 2 ms 908 KB Output is correct
10 Correct 2 ms 908 KB Output is correct
11 Correct 2 ms 908 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 900 KB Output is correct
15 Correct 2 ms 908 KB Output is correct
16 Incorrect 2 ms 908 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 13948 KB Output is correct
2 Correct 50 ms 14580 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 36 ms 13980 KB Output is correct
5 Correct 45 ms 15216 KB Output is correct
6 Correct 46 ms 15380 KB Output is correct
7 Incorrect 38 ms 14468 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14016 KB Output is correct
2 Incorrect 46 ms 14040 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -