oj.uz

답안 #786653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786653 2023-07-18T10:55:34 Z JoenPoenMan 길고양이 (JOI20_stray) C++17
20 / 100
 51 ms 18740 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] == 1 && prevA != 0 ? 0 : (y[1] == 1 && prevA != 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

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 17608 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 17156 KB Output is correct
4 Correct 47 ms 18680 KB Output is correct
5 Correct 47 ms 18740 KB Output is correct
6 Correct 41 ms 17444 KB Output is correct
7 Correct 45 ms 17408 KB Output is correct
8 Correct 47 ms 18192 KB Output is correct
9 Correct 47 ms 18072 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 17608 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 37 ms 17156 KB Output is correct
4 Correct 47 ms 18680 KB Output is correct
5 Correct 47 ms 18740 KB Output is correct
6 Correct 41 ms 17444 KB Output is correct
7 Correct 45 ms 17408 KB Output is correct
8 Correct 47 ms 18192 KB Output is correct
9 Correct 47 ms 18072 KB Output is correct
10 Correct 40 ms 15600 KB Output is correct
11 Correct 40 ms 15584 KB Output is correct
12 Correct 40 ms 15548 KB Output is correct
13 Correct 40 ms 15528 KB Output is correct
14 Correct 39 ms 15712 KB Output is correct
15 Correct 50 ms 16124 KB Output is correct
16 Correct 44 ms 18192 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 15292 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 37 ms 15068 KB Output is correct
4 Correct 47 ms 16632 KB Output is correct
5 Correct 47 ms 16608 KB Output is correct
6 Correct 41 ms 15316 KB Output is correct
7 Correct 47 ms 15448 KB Output is correct
8 Correct 45 ms 15780 KB Output is correct
9 Correct 51 ms 15852 KB Output is correct
10 Correct 43 ms 15600 KB Output is correct
11 Correct 43 ms 15644 KB Output is correct
12 Correct 41 ms 15584 KB Output is correct
13 Correct 43 ms 15596 KB Output is correct
14 Correct 48 ms 15828 KB Output is correct
15 Correct 44 ms 15960 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 15292 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 37 ms 15068 KB Output is correct
4 Correct 47 ms 16632 KB Output is correct
5 Correct 47 ms 16608 KB Output is correct
6 Correct 41 ms 15316 KB Output is correct
7 Correct 47 ms 15448 KB Output is correct
8 Correct 45 ms 15780 KB Output is correct
9 Correct 51 ms 15852 KB Output is correct
10 Correct 43 ms 15600 KB Output is correct
11 Correct 43 ms 15644 KB Output is correct
12 Correct 41 ms 15584 KB Output is correct
13 Correct 43 ms 15596 KB Output is correct
14 Correct 48 ms 15828 KB Output is correct
15 Correct 44 ms 15960 KB Output is correct
16 Correct 39 ms 13768 KB Output is correct
17 Correct 38 ms 13756 KB Output is correct
18 Correct 39 ms 13584 KB Output is correct
19 Correct 39 ms 13560 KB Output is correct
20 Correct 43 ms 14260 KB Output is correct
21 Correct 39 ms 13932 KB Output is correct
22 Correct 49 ms 16108 KB Output is correct
23 Correct 48 ms 13684 KB Output is correct
24 Correct 51 ms 13740 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 904 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 904 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 892 KB Output is correct
12 Correct 2 ms 908 KB Output is correct
13 Correct 2 ms 896 KB Output is correct
14 Correct 2 ms 896 KB Output is correct
15 Correct 2 ms 896 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 2 ms 908 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 2 ms 908 KB Output is correct
21 Correct 2 ms 900 KB Output is correct
22 Correct 2 ms 900 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 964 KB Output is correct
25 Correct 2 ms 900 KB Output is correct
26 Correct 2 ms 908 KB Output is correct
27 Correct 2 ms 900 KB Output is correct
28 Correct 2 ms 864 KB Output is correct

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 13572 KB Output is correct
2 Correct 41 ms 13832 KB Output is correct
3 Correct 1 ms 520 KB Output is correct
4 Correct 36 ms 13916 KB Output is correct
5 Correct 46 ms 15308 KB Output is correct
6 Correct 45 ms 15324 KB Output is correct
7 Incorrect 37 ms 14608 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 13564 KB Output is correct
2 Correct 40 ms 14232 KB Output is correct
3 Correct 0 ms 520 KB Output is correct
4 Correct 40 ms 13812 KB Output is correct
5 Correct 47 ms 15408 KB Output is correct
6 Correct 46 ms 15220 KB Output is correct
7 Incorrect 38 ms 14592 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -