oj.uz

Submission #786970

# Submission time Handle Problem Language Result Execution time Memory
786970 2023-07-18T15:51:23 Z JoenPoenMan Stray Cat (JOI20_stray) C++17
100 / 100
 61 ms 18752 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) {
                        if (straightlength == 0 && *marker[pos] == true) straightlength++;
                        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 {
            if (y[0] + y[1] == 1) {
                return (y[0] ? 0 : 1);
            } 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:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         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 41 ms 17656 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 39 ms 17228 KB Output is correct
4 Correct 57 ms 18752 KB Output is correct
5 Correct 51 ms 18708 KB Output is correct
6 Correct 41 ms 17396 KB Output is correct
7 Correct 41 ms 17524 KB Output is correct
8 Correct 45 ms 18172 KB Output is correct
9 Correct 46 ms 18072 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17656 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 39 ms 17228 KB Output is correct
4 Correct 57 ms 18752 KB Output is correct
5 Correct 51 ms 18708 KB Output is correct
6 Correct 41 ms 17396 KB Output is correct
7 Correct 41 ms 17524 KB Output is correct
8 Correct 45 ms 18172 KB Output is correct
9 Correct 46 ms 18072 KB Output is correct
10 Correct 46 ms 15616 KB Output is correct
11 Correct 40 ms 15544 KB Output is correct
12 Correct 39 ms 15508 KB Output is correct
13 Correct 41 ms 15396 KB Output is correct
14 Correct 40 ms 15852 KB Output is correct
15 Correct 61 ms 16104 KB Output is correct
16 Correct 45 ms 18328 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15204 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 45 ms 14908 KB Output is correct
4 Correct 45 ms 16632 KB Output is correct
5 Correct 45 ms 16596 KB Output is correct
6 Correct 48 ms 15268 KB Output is correct
7 Correct 41 ms 15288 KB Output is correct
8 Correct 43 ms 15832 KB Output is correct
9 Correct 50 ms 15840 KB Output is correct
10 Correct 43 ms 15496 KB Output is correct
11 Correct 48 ms 15628 KB Output is correct
12 Correct 43 ms 15684 KB Output is correct
13 Correct 43 ms 15608 KB Output is correct
14 Correct 45 ms 16016 KB Output is correct
15 Correct 45 ms 15868 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15204 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 45 ms 14908 KB Output is correct
4 Correct 45 ms 16632 KB Output is correct
5 Correct 45 ms 16596 KB Output is correct
6 Correct 48 ms 15268 KB Output is correct
7 Correct 41 ms 15288 KB Output is correct
8 Correct 43 ms 15832 KB Output is correct
9 Correct 50 ms 15840 KB Output is correct
10 Correct 43 ms 15496 KB Output is correct
11 Correct 48 ms 15628 KB Output is correct
12 Correct 43 ms 15684 KB Output is correct
13 Correct 43 ms 15608 KB Output is correct
14 Correct 45 ms 16016 KB Output is correct
15 Correct 45 ms 15868 KB Output is correct
16 Correct 38 ms 13800 KB Output is correct
17 Correct 37 ms 13828 KB Output is correct
18 Correct 38 ms 13612 KB Output is correct
19 Correct 40 ms 13604 KB Output is correct
20 Correct 41 ms 14184 KB Output is correct
21 Correct 52 ms 13896 KB Output is correct
22 Correct 43 ms 16028 KB Output is correct
23 Correct 44 ms 13728 KB Output is correct
24 Correct 40 ms 13744 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 908 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 900 KB Output is correct
6 Correct 2 ms 908 KB Output is correct
7 Correct 2 ms 908 KB Output is correct
8 Correct 2 ms 908 KB Output is correct
9 Correct 2 ms 908 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 3 ms 904 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 900 KB Output is correct
19 Correct 2 ms 908 KB Output is correct
20 Correct 2 ms 864 KB Output is correct
21 Correct 2 ms 892 KB Output is correct
22 Correct 2 ms 908 KB Output is correct
23 Correct 2 ms 920 KB Output is correct
24 Correct 2 ms 868 KB Output is correct
25 Correct 2 ms 864 KB Output is correct
26 Correct 2 ms 900 KB Output is correct
27 Correct 2 ms 900 KB Output is correct
28 Correct 2 ms 908 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13356 KB Output is correct
2 Correct 44 ms 14192 KB Output is correct
3 Correct 0 ms 520 KB Output is correct
4 Correct 33 ms 13624 KB Output is correct
5 Correct 41 ms 14896 KB Output is correct
6 Correct 41 ms 14904 KB Output is correct
7 Correct 43 ms 14012 KB Output is correct
8 Correct 39 ms 14040 KB Output is correct
9 Correct 44 ms 14844 KB Output is correct
10 Correct 43 ms 15012 KB Output is correct
11 Correct 41 ms 14832 KB Output is correct
12 Correct 43 ms 14904 KB Output is correct
13 Correct 51 ms 14916 KB Output is correct
14 Correct 43 ms 14900 KB Output is correct
15 Correct 41 ms 14848 KB Output is correct
16 Correct 41 ms 14908 KB Output is correct
17 Correct 39 ms 14648 KB Output is correct
18 Correct 39 ms 14548 KB Output is correct
19 Correct 47 ms 14652 KB Output is correct
20 Correct 41 ms 14684 KB Output is correct
21 Correct 40 ms 14660 KB Output is correct
22 Correct 40 ms 14588 KB Output is correct
23 Correct 36 ms 13848 KB Output is correct
24 Correct 36 ms 13764 KB Output is correct
25 Correct 37 ms 13928 KB Output is correct
26 Correct 39 ms 13932 KB Output is correct
27 Correct 40 ms 14396 KB Output is correct
28 Correct 44 ms 14296 KB Output is correct
29 Correct 39 ms 14532 KB Output is correct
30 Correct 39 ms 14536 KB Output is correct
31 Correct 38 ms 13880 KB Output is correct
32 Correct 38 ms 13808 KB Output is correct
33 Correct 37 ms 13772 KB Output is correct
34 Correct 36 ms 13824 KB Output is correct
35 Correct 39 ms 14368 KB Output is correct
36 Correct 48 ms 14512 KB Output is correct
37 Correct 39 ms 14356 KB Output is correct
38 Correct 39 ms 14336 KB Output is correct
39 Correct 51 ms 14268 KB Output is correct
40 Correct 39 ms 14392 KB Output is correct
41 Correct 39 ms 14704 KB Output is correct
42 Correct 40 ms 14560 KB Output is correct
43 Correct 39 ms 14644 KB Output is correct
44 Correct 45 ms 14620 KB Output is correct
45 Correct 44 ms 14516 KB Output is correct
46 Correct 39 ms 14660 KB Output is correct
47 Correct 39 ms 14140 KB Output is correct
48 Correct 45 ms 14240 KB Output is correct
49 Correct 54 ms 14256 KB Output is correct
50 Correct 39 ms 14300 KB Output is correct
51 Correct 37 ms 13944 KB Output is correct
52 Correct 37 ms 13900 KB Output is correct
53 Correct 37 ms 14024 KB Output is correct
54 Correct 40 ms 13928 KB Output is correct
55 Correct 37 ms 13884 KB Output is correct
56 Correct 37 ms 14020 KB Output is correct
57 Correct 45 ms 13928 KB Output is correct
58 Correct 38 ms 14008 KB Output is correct
59 Correct 37 ms 13984 KB Output is correct
60 Correct 39 ms 14040 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13344 KB Output is correct
2 Correct 44 ms 14184 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 32 ms 13732 KB Output is correct
5 Correct 45 ms 14900 KB Output is correct
6 Correct 46 ms 14856 KB Output is correct
7 Correct 38 ms 13976 KB Output is correct
8 Correct 37 ms 13960 KB Output is correct
9 Correct 48 ms 14884 KB Output is correct
10 Correct 41 ms 14884 KB Output is correct
11 Correct 54 ms 14936 KB Output is correct
12 Correct 41 ms 14992 KB Output is correct
13 Correct 46 ms 14856 KB Output is correct
14 Correct 43 ms 14804 KB Output is correct
15 Correct 41 ms 14904 KB Output is correct
16 Correct 43 ms 14936 KB Output is correct
17 Correct 45 ms 14588 KB Output is correct
18 Correct 49 ms 14580 KB Output is correct
19 Correct 39 ms 14580 KB Output is correct
20 Correct 40 ms 14660 KB Output is correct
21 Correct 40 ms 14616 KB Output is correct
22 Correct 39 ms 14704 KB Output is correct
23 Correct 37 ms 13772 KB Output is correct
24 Correct 37 ms 13684 KB Output is correct
25 Correct 39 ms 13896 KB Output is correct
26 Correct 38 ms 13940 KB Output is correct
27 Correct 43 ms 14380 KB Output is correct
28 Correct 39 ms 14324 KB Output is correct
29 Correct 40 ms 14384 KB Output is correct
30 Correct 41 ms 14476 KB Output is correct
31 Correct 37 ms 13780 KB Output is correct
32 Correct 39 ms 13776 KB Output is correct
33 Correct 38 ms 13912 KB Output is correct
34 Correct 38 ms 13972 KB Output is correct
35 Correct 46 ms 14344 KB Output is correct
36 Correct 39 ms 14324 KB Output is correct
37 Correct 40 ms 14376 KB Output is correct
38 Correct 39 ms 14320 KB Output is correct
39 Correct 45 ms 14400 KB Output is correct
40 Correct 45 ms 14444 KB Output is correct
41 Correct 40 ms 14548 KB Output is correct
42 Correct 44 ms 14536 KB Output is correct
43 Correct 40 ms 14688 KB Output is correct
44 Correct 41 ms 14540 KB Output is correct
45 Correct 40 ms 14604 KB Output is correct
46 Correct 49 ms 14668 KB Output is correct
47 Correct 39 ms 14260 KB Output is correct
48 Correct 39 ms 14208 KB Output is correct
49 Correct 38 ms 14164 KB Output is correct
50 Correct 40 ms 14292 KB Output is correct
51 Correct 38 ms 14000 KB Output is correct
52 Correct 40 ms 13972 KB Output is correct
53 Correct 43 ms 14012 KB Output is correct
54 Correct 39 ms 14012 KB Output is correct
55 Correct 38 ms 13940 KB Output is correct
56 Correct 47 ms 13892 KB Output is correct
57 Correct 40 ms 13876 KB Output is correct
58 Correct 37 ms 13992 KB Output is correct
59 Correct 38 ms 13988 KB Output is correct
60 Correct 39 ms 14004 KB Output is correct