oj.uz

Submission #782963

# Submission time Handle Problem Language Result Execution time Memory
782963 2023-07-14T13:04:15 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 62 ms 22196 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;
    }

    int A2(vector<int> y) {
        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;
        }
    }

} // namespace

void Init(int A, int B)
{
    ::A = A;
    ::B = B;
}

int Move(std::vector<int> y)
{
    if (A==2) {
        int res = ::A2(y);
        if (!((res==0&&y[0])||(res==1&&y[1]))) {
            cerr << res << ' ' << y[0] << ' ' << y[1] << endl;
        }
    } 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:66:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
      |                          ~~^~~~~~~~~~
Catherine.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17576 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 43 ms 17176 KB Output is correct
4 Correct 52 ms 18652 KB Output is correct
5 Correct 51 ms 18676 KB Output is correct
6 Correct 53 ms 17452 KB Output is correct
7 Correct 53 ms 17380 KB Output is correct
8 Correct 49 ms 18044 KB Output is correct
9 Correct 62 ms 18096 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17576 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 43 ms 17176 KB Output is correct
4 Correct 52 ms 18652 KB Output is correct
5 Correct 51 ms 18676 KB Output is correct
6 Correct 53 ms 17452 KB Output is correct
7 Correct 53 ms 17380 KB Output is correct
8 Correct 49 ms 18044 KB Output is correct
9 Correct 62 ms 18096 KB Output is correct
10 Correct 44 ms 15428 KB Output is correct
11 Correct 41 ms 15544 KB Output is correct
12 Correct 50 ms 15552 KB Output is correct
13 Correct 40 ms 15588 KB Output is correct
14 Correct 41 ms 15728 KB Output is correct
15 Correct 47 ms 16044 KB Output is correct
16 Correct 61 ms 18324 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15216 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 38 ms 14952 KB Output is correct
4 Correct 61 ms 16572 KB Output is correct
5 Correct 56 ms 16440 KB Output is correct
6 Correct 52 ms 15308 KB Output is correct
7 Correct 41 ms 15244 KB Output is correct
8 Correct 46 ms 15920 KB Output is correct
9 Correct 49 ms 15760 KB Output is correct
10 Correct 46 ms 15588 KB Output is correct
11 Correct 47 ms 15572 KB Output is correct
12 Correct 46 ms 15508 KB Output is correct
13 Correct 53 ms 15688 KB Output is correct
14 Correct 58 ms 15816 KB Output is correct
15 Correct 52 ms 15948 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15216 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 38 ms 14952 KB Output is correct
4 Correct 61 ms 16572 KB Output is correct
5 Correct 56 ms 16440 KB Output is correct
6 Correct 52 ms 15308 KB Output is correct
7 Correct 41 ms 15244 KB Output is correct
8 Correct 46 ms 15920 KB Output is correct
9 Correct 49 ms 15760 KB Output is correct
10 Correct 46 ms 15588 KB Output is correct
11 Correct 47 ms 15572 KB Output is correct
12 Correct 46 ms 15508 KB Output is correct
13 Correct 53 ms 15688 KB Output is correct
14 Correct 58 ms 15816 KB Output is correct
15 Correct 52 ms 15948 KB Output is correct
16 Correct 38 ms 13792 KB Output is correct
17 Correct 38 ms 13832 KB Output is correct
18 Correct 40 ms 13664 KB Output is correct
19 Correct 41 ms 13580 KB Output is correct
20 Correct 44 ms 14172 KB Output is correct
21 Correct 40 ms 13932 KB Output is correct
22 Correct 46 ms 16088 KB Output is correct
23 Correct 40 ms 13660 KB Output is correct
24 Correct 42 ms 13700 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1408 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 22184 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 22196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -