oj.uz

Submission #786650

# Submission time Handle Problem Language Result Execution time Memory
786650 2023-07-18T10:52:56 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 51 ms 19164 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 findNext2(vector<int> y) {
        if (!::onPath) {
            if (::first) {
                ::first = false;
                if (y[0]+y[1] != 2) {
                    ::onPath = true;
                    return (y[0] == 1 ? 0 : 1);
                }
                return 0;
            }
            if (y[0] + y[1] > 1) {
                ::onPath = true;
                return (y[0] + (prevA ? 0 : 1) == 1 ? 0 : (y[1] + (prevA ? 1 : 0) == 1 ? 1 : -1));
            } else if (y[0] + y[1] == 0) {
                ::onPath = true;
                return -1;
            } else {
                return !::prevA;
            }
        } else {
            return !::prevA;
        }
    }

} 

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

int Move(std::vector<int> y)
{
    if (A==2) {
        int res = ::findNext2(y);
        if (res != -1) ::prevA = res;
        return res;
    } 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:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         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 18116 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 43 ms 17568 KB Output is correct
4 Correct 49 ms 19072 KB Output is correct
5 Correct 49 ms 19164 KB Output is correct
6 Correct 44 ms 17848 KB Output is correct
7 Correct 43 ms 17844 KB Output is correct
8 Correct 48 ms 18528 KB Output is correct
9 Correct 46 ms 18564 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18116 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 43 ms 17568 KB Output is correct
4 Correct 49 ms 19072 KB Output is correct
5 Correct 49 ms 19164 KB Output is correct
6 Correct 44 ms 17848 KB Output is correct
7 Correct 43 ms 17844 KB Output is correct
8 Correct 48 ms 18528 KB Output is correct
9 Correct 46 ms 18564 KB Output is correct
10 Correct 40 ms 15932 KB Output is correct
11 Correct 41 ms 16056 KB Output is correct
12 Correct 41 ms 15928 KB Output is correct
13 Correct 42 ms 15916 KB Output is correct
14 Correct 42 ms 16196 KB Output is correct
15 Correct 44 ms 16576 KB Output is correct
16 Correct 44 ms 18696 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15684 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 37 ms 15352 KB Output is correct
4 Correct 47 ms 16976 KB Output is correct
5 Correct 46 ms 17008 KB Output is correct
6 Correct 41 ms 15600 KB Output is correct
7 Correct 43 ms 15648 KB Output is correct
8 Correct 45 ms 16284 KB Output is correct
9 Correct 45 ms 16316 KB Output is correct
10 Correct 43 ms 16060 KB Output is correct
11 Correct 43 ms 16128 KB Output is correct
12 Correct 44 ms 16048 KB Output is correct
13 Correct 44 ms 15984 KB Output is correct
14 Correct 51 ms 16372 KB Output is correct
15 Correct 45 ms 16404 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15684 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 37 ms 15352 KB Output is correct
4 Correct 47 ms 16976 KB Output is correct
5 Correct 46 ms 17008 KB Output is correct
6 Correct 41 ms 15600 KB Output is correct
7 Correct 43 ms 15648 KB Output is correct
8 Correct 45 ms 16284 KB Output is correct
9 Correct 45 ms 16316 KB Output is correct
10 Correct 43 ms 16060 KB Output is correct
11 Correct 43 ms 16128 KB Output is correct
12 Correct 44 ms 16048 KB Output is correct
13 Correct 44 ms 15984 KB Output is correct
14 Correct 51 ms 16372 KB Output is correct
15 Correct 45 ms 16404 KB Output is correct
16 Correct 39 ms 14288 KB Output is correct
17 Correct 38 ms 14312 KB Output is correct
18 Correct 39 ms 13996 KB Output is correct
19 Correct 40 ms 13928 KB Output is correct
20 Correct 41 ms 14632 KB Output is correct
21 Correct 44 ms 14444 KB Output is correct
22 Correct 44 ms 16364 KB Output is correct
23 Correct 39 ms 14088 KB Output is correct
24 Correct 40 ms 14056 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 872 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 2 ms 900 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 900 KB Output is correct
7 Correct 2 ms 900 KB Output is correct
8 Correct 2 ms 884 KB Output is correct
9 Correct 2 ms 904 KB Output is correct
10 Correct 2 ms 908 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 920 KB Output is correct
14 Incorrect 2 ms 900 KB Wrong Answer [5]
15 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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