oj.uz

Submission #782984

# Submission time Handle Problem Language Result Execution time Memory
782984 2023-07-14T13:38:52 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 60 ms 18772 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 (y[0]==0 ^ y[1]==0) {
                if (::first) {
                    ::onPath = true;
                    ::prevA = y[0]?0:1;
                    return y[0]?0:1;
                } else {
                    ::prevA = !::prevA;
                    return ::prevA;
                }
            }
            if (y[0]==1 && y[1]==1) {
                return 0;
            } 
            if (y[0]==0 && y[1]==0) {
                return -1;
            }
            ::prevA = y[0]==1?0:1;
        } 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:27:21: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   27 |             if (y[0]==0 ^ y[1]==0) {
Catherine.cpp:51:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
      |                          ~~^~~~~~~~~~
Catherine.cpp:43:21: warning: control reaches end of non-void function [-Wreturn-type]
   43 |             ::prevA = y[0]==1?0:1;
      |             ~~~~~~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17584 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 47 ms 17240 KB Output is correct
4 Correct 54 ms 18660 KB Output is correct
5 Correct 56 ms 18772 KB Output is correct
6 Correct 48 ms 17376 KB Output is correct
7 Correct 45 ms 17416 KB Output is correct
8 Correct 47 ms 18212 KB Output is correct
9 Correct 60 ms 18072 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17584 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 47 ms 17240 KB Output is correct
4 Correct 54 ms 18660 KB Output is correct
5 Correct 56 ms 18772 KB Output is correct
6 Correct 48 ms 17376 KB Output is correct
7 Correct 45 ms 17416 KB Output is correct
8 Correct 47 ms 18212 KB Output is correct
9 Correct 60 ms 18072 KB Output is correct
10 Correct 41 ms 15464 KB Output is correct
11 Correct 45 ms 15560 KB Output is correct
12 Correct 41 ms 15580 KB Output is correct
13 Correct 41 ms 15396 KB Output is correct
14 Correct 41 ms 15720 KB Output is correct
15 Correct 50 ms 16184 KB Output is correct
16 Correct 44 ms 18296 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15224 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 37 ms 15088 KB Output is correct
4 Correct 48 ms 16540 KB Output is correct
5 Correct 51 ms 16596 KB Output is correct
6 Correct 45 ms 15304 KB Output is correct
7 Correct 43 ms 15260 KB Output is correct
8 Correct 47 ms 15980 KB Output is correct
9 Correct 51 ms 15772 KB Output is correct
10 Correct 43 ms 15640 KB Output is correct
11 Correct 43 ms 15640 KB Output is correct
12 Correct 43 ms 15528 KB Output is correct
13 Correct 44 ms 15576 KB Output is correct
14 Correct 46 ms 15920 KB Output is correct
15 Correct 55 ms 15848 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15224 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 37 ms 15088 KB Output is correct
4 Correct 48 ms 16540 KB Output is correct
5 Correct 51 ms 16596 KB Output is correct
6 Correct 45 ms 15304 KB Output is correct
7 Correct 43 ms 15260 KB Output is correct
8 Correct 47 ms 15980 KB Output is correct
9 Correct 51 ms 15772 KB Output is correct
10 Correct 43 ms 15640 KB Output is correct
11 Correct 43 ms 15640 KB Output is correct
12 Correct 43 ms 15528 KB Output is correct
13 Correct 44 ms 15576 KB Output is correct
14 Correct 46 ms 15920 KB Output is correct
15 Correct 55 ms 15848 KB Output is correct
16 Correct 40 ms 13780 KB Output is correct
17 Correct 40 ms 13892 KB Output is correct
18 Correct 41 ms 13644 KB Output is correct
19 Correct 40 ms 13604 KB Output is correct
20 Correct 43 ms 14216 KB Output is correct
21 Correct 43 ms 13876 KB Output is correct
22 Correct 44 ms 15988 KB Output is correct
23 Correct 41 ms 13676 KB Output is correct
24 Correct 41 ms 13728 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 13644 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -