oj.uz

Submission #782998

# Submission time Handle Problem Language Result Execution time Memory
782998 2023-07-14T13:56:04 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 50 ms 18812 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 44 ms 17596 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 17300 KB Output is correct
4 Correct 49 ms 18812 KB Output is correct
5 Correct 49 ms 18784 KB Output is correct
6 Correct 43 ms 17456 KB Output is correct
7 Correct 41 ms 17516 KB Output is correct
8 Correct 46 ms 18100 KB Output is correct
9 Correct 46 ms 18180 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 17596 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 17300 KB Output is correct
4 Correct 49 ms 18812 KB Output is correct
5 Correct 49 ms 18784 KB Output is correct
6 Correct 43 ms 17456 KB Output is correct
7 Correct 41 ms 17516 KB Output is correct
8 Correct 46 ms 18100 KB Output is correct
9 Correct 46 ms 18180 KB Output is correct
10 Correct 41 ms 15484 KB Output is correct
11 Correct 41 ms 15588 KB Output is correct
12 Correct 40 ms 15612 KB Output is correct
13 Correct 41 ms 15516 KB Output is correct
14 Correct 40 ms 15764 KB Output is correct
15 Correct 43 ms 16104 KB Output is correct
16 Correct 48 ms 18304 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15248 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 36 ms 15092 KB Output is correct
4 Correct 46 ms 16492 KB Output is correct
5 Correct 46 ms 16408 KB Output is correct
6 Correct 41 ms 15308 KB Output is correct
7 Correct 41 ms 15316 KB Output is correct
8 Correct 44 ms 15940 KB Output is correct
9 Correct 43 ms 15864 KB Output is correct
10 Correct 41 ms 15592 KB Output is correct
11 Correct 43 ms 15592 KB Output is correct
12 Correct 43 ms 15672 KB Output is correct
13 Correct 41 ms 15588 KB Output is correct
14 Correct 45 ms 15968 KB Output is correct
15 Correct 50 ms 16084 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15248 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 36 ms 15092 KB Output is correct
4 Correct 46 ms 16492 KB Output is correct
5 Correct 46 ms 16408 KB Output is correct
6 Correct 41 ms 15308 KB Output is correct
7 Correct 41 ms 15316 KB Output is correct
8 Correct 44 ms 15940 KB Output is correct
9 Correct 43 ms 15864 KB Output is correct
10 Correct 41 ms 15592 KB Output is correct
11 Correct 43 ms 15592 KB Output is correct
12 Correct 43 ms 15672 KB Output is correct
13 Correct 41 ms 15588 KB Output is correct
14 Correct 45 ms 15968 KB Output is correct
15 Correct 50 ms 16084 KB Output is correct
16 Correct 39 ms 13860 KB Output is correct
17 Correct 38 ms 13788 KB Output is correct
18 Correct 39 ms 13664 KB Output is correct
19 Correct 39 ms 13652 KB Output is correct
20 Correct 40 ms 14160 KB Output is correct
21 Correct 40 ms 14036 KB Output is correct
22 Correct 46 ms 16172 KB Output is correct
23 Correct 40 ms 13648 KB Output is correct
24 Correct 45 ms 13580 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #7
0 / 9.0

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