oj.uz

Submission #782994

# Submission time Handle Problem Language Result Execution time Memory
782994 2023-07-14T13:50:37 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 57 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:51:32: 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:25: 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 45 ms 17532 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 39 ms 17204 KB Output is correct
4 Correct 49 ms 18740 KB Output is correct
5 Correct 56 ms 18772 KB Output is correct
6 Correct 49 ms 17432 KB Output is correct
7 Correct 44 ms 17344 KB Output is correct
8 Correct 49 ms 18100 KB Output is correct
9 Correct 49 ms 18212 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 17532 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 39 ms 17204 KB Output is correct
4 Correct 49 ms 18740 KB Output is correct
5 Correct 56 ms 18772 KB Output is correct
6 Correct 49 ms 17432 KB Output is correct
7 Correct 44 ms 17344 KB Output is correct
8 Correct 49 ms 18100 KB Output is correct
9 Correct 49 ms 18212 KB Output is correct
10 Correct 40 ms 15568 KB Output is correct
11 Correct 41 ms 15564 KB Output is correct
12 Correct 41 ms 15584 KB Output is correct
13 Correct 40 ms 15532 KB Output is correct
14 Correct 41 ms 15720 KB Output is correct
15 Correct 43 ms 16216 KB Output is correct
16 Correct 44 ms 18204 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15332 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 44 ms 14992 KB Output is correct
4 Correct 57 ms 16492 KB Output is correct
5 Correct 55 ms 16436 KB Output is correct
6 Correct 43 ms 15192 KB Output is correct
7 Correct 41 ms 15264 KB Output is correct
8 Correct 46 ms 15876 KB Output is correct
9 Correct 45 ms 15860 KB Output is correct
10 Correct 50 ms 15496 KB Output is correct
11 Correct 45 ms 15520 KB Output is correct
12 Correct 47 ms 15548 KB Output is correct
13 Correct 48 ms 15512 KB Output is correct
14 Correct 45 ms 16036 KB Output is correct
15 Correct 45 ms 16016 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15332 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 44 ms 14992 KB Output is correct
4 Correct 57 ms 16492 KB Output is correct
5 Correct 55 ms 16436 KB Output is correct
6 Correct 43 ms 15192 KB Output is correct
7 Correct 41 ms 15264 KB Output is correct
8 Correct 46 ms 15876 KB Output is correct
9 Correct 45 ms 15860 KB Output is correct
10 Correct 50 ms 15496 KB Output is correct
11 Correct 45 ms 15520 KB Output is correct
12 Correct 47 ms 15548 KB Output is correct
13 Correct 48 ms 15512 KB Output is correct
14 Correct 45 ms 16036 KB Output is correct
15 Correct 45 ms 16016 KB Output is correct
16 Correct 39 ms 13832 KB Output is correct
17 Correct 46 ms 13788 KB Output is correct
18 Correct 40 ms 13588 KB Output is correct
19 Correct 39 ms 13608 KB Output is correct
20 Correct 40 ms 14204 KB Output is correct
21 Correct 41 ms 13916 KB Output is correct
22 Correct 43 ms 16032 KB Output is correct
23 Correct 42 ms 13684 KB Output is correct
24 Correct 40 ms 13740 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 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 39 ms 13500 KB Output is correct
2 Incorrect 38 ms 13652 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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