oj.uz

Submission #786962

# Submission time Handle Problem Language Result Execution time Memory
786962 2023-07-18T15:42:13 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
15 / 100
 56 ms 19084 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);
    if (A == 2) {
        vector<optional<bool>> marker(N);
        vector<int> prev (N, -1);
        int straightlength = 0;
        bool pattern[6] = {true, false, true, true, false, false};
        stack<int> s;
        s.push(0);
        marker[0] = false;
        while (!s.empty()) {
            int pos = s.top();
            s.pop();
            for (auto [other, ind] : ADJ[pos]) {
                if (!marker[other]) {
                    s.push(other);
                    prev[other] = pos;
                    if (ADJ[pos].size() <= 2) {
                        marker[other] = pattern[straightlength%6];

                        straightlength++;
                    } else {
                        straightlength = 0;
                        marker[other] = !(*marker[pos]);
                    }
                }

            }
        }

        for (int i = 1; i < N; i++) {
            X[paths[{i, prev[i]}]] = (*marker[i]);
        }
        return X;
    }

    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;
    bool code[5];
    int codeCount = 2;

    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);
                }
                if (y[0] == 2) {
                    code[0] = false, code[1] = false;
                    return 0;
                }
                if (y[1] == 2) code[0] = false, code[1] = false;
                else code[0] = false, code[1] = true;
                return 1;
            }
            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 {
                code[codeCount] = (y[0] ? 0 : 1);
                codeCount++;
                if (codeCount == 5) {
                    onPath = true;
                    return (code[4] == 0 ? -1 : 1);
                }
                if (codeCount == 4) {
                    ::onPath = true;
                    if (code[0] == 0 && code[1] == 0) {
                        if (code[3] == 0) return -1;
                        else return 1;
                    }
                    if (code[0] && code[1]) {
                        if (code[3] == 0) return -1;
                        else return 1;
                    }
                    if (code[2] == 0) {
                        if (code[3] == 1) return -1;
                        else return 0;
                    }
                    onPath = false;
                }
                return (y[0] ? 0 : 1);
            }
        } else {
            return (y[0] ? 0 : 1);
        }
    }

} 

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:86:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         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 18128 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 44 ms 17624 KB Output is correct
4 Correct 47 ms 19056 KB Output is correct
5 Correct 47 ms 19084 KB Output is correct
6 Correct 41 ms 17760 KB Output is correct
7 Correct 44 ms 17784 KB Output is correct
8 Correct 45 ms 18612 KB Output is correct
9 Correct 45 ms 18580 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18128 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 44 ms 17624 KB Output is correct
4 Correct 47 ms 19056 KB Output is correct
5 Correct 47 ms 19084 KB Output is correct
6 Correct 41 ms 17760 KB Output is correct
7 Correct 44 ms 17784 KB Output is correct
8 Correct 45 ms 18612 KB Output is correct
9 Correct 45 ms 18580 KB Output is correct
10 Correct 38 ms 16048 KB Output is correct
11 Correct 39 ms 16012 KB Output is correct
12 Correct 39 ms 16000 KB Output is correct
13 Correct 40 ms 15868 KB Output is correct
14 Correct 40 ms 16256 KB Output is correct
15 Correct 46 ms 16556 KB Output is correct
16 Correct 56 ms 18536 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15564 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 36 ms 15452 KB Output is correct
4 Correct 45 ms 16992 KB Output is correct
5 Correct 47 ms 17052 KB Output is correct
6 Correct 44 ms 15588 KB Output is correct
7 Correct 41 ms 15596 KB Output is correct
8 Correct 45 ms 16312 KB Output is correct
9 Correct 43 ms 16312 KB Output is correct
10 Correct 41 ms 16080 KB Output is correct
11 Correct 43 ms 16060 KB Output is correct
12 Correct 43 ms 16064 KB Output is correct
13 Correct 43 ms 16060 KB Output is correct
14 Correct 48 ms 16420 KB Output is correct
15 Correct 44 ms 16400 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15564 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 36 ms 15452 KB Output is correct
4 Correct 45 ms 16992 KB Output is correct
5 Correct 47 ms 17052 KB Output is correct
6 Correct 44 ms 15588 KB Output is correct
7 Correct 41 ms 15596 KB Output is correct
8 Correct 45 ms 16312 KB Output is correct
9 Correct 43 ms 16312 KB Output is correct
10 Correct 41 ms 16080 KB Output is correct
11 Correct 43 ms 16060 KB Output is correct
12 Correct 43 ms 16064 KB Output is correct
13 Correct 43 ms 16060 KB Output is correct
14 Correct 48 ms 16420 KB Output is correct
15 Correct 44 ms 16400 KB Output is correct
16 Correct 39 ms 14124 KB Output is correct
17 Correct 37 ms 14268 KB Output is correct
18 Correct 43 ms 13928 KB Output is correct
19 Correct 39 ms 14056 KB Output is correct
20 Correct 40 ms 14624 KB Output is correct
21 Correct 39 ms 14384 KB Output is correct
22 Correct 45 ms 16492 KB Output is correct
23 Correct 40 ms 14040 KB Output is correct
24 Correct 41 ms 14104 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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