oj.uz

답안 #747827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747827 2023-05-24T21:02:16 Z finn__ 길고양이 (JOI20_stray) C++17
15 / 100
 53 ms 16268 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

constexpr bool pattern[6] = {0, 0, 1, 1, 0, 1};

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v)
{
    vector<vector<int>> g(n);
    for (size_t i = 0; i < m; ++i)
        g[u[i]].push_back(v[i]), g[v[i]].push_back(u[i]);

    queue<int> q;
    q.push(0);
    vector<int> d(n, -1), pattern_index(n, -1);
    vector<bool> color(n, 0);
    d[0] = pattern_index[0] = 0;
    while (!q.empty())
    {
        int const x = q.front();
        q.pop();

        for (auto const &y : g[x])
            if (d[y] == -1)
            {
                d[y] = d[x] + 1;
                q.push(y);

                if (g[y].size() <= 2)
                {
                    pattern_index[y] = (pattern_index[x] + 1) % 6;
                    color[y] = color[x];
                }
                else
                {
                    pattern_index[y] = pattern_index[x];
                    color[y] = !color[x];
                }
            }
    }

    vector<int> ans(m);
    if (a >= 3)
    {
        for (size_t i = 0; i < m; ++i)
            ans[i] = min(d[u[i]], d[v[i]]) % 3;
    }
    else
    {
        for (size_t i = 0; i < m; ++i)
        {
            if (d[u[i]] > d[v[i]])
                swap(u[i], v[i]);
            ans[i] = pattern[pattern_index[u[i]]] ^ color[u[i]];
        }
    }

    return ans;
}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

bool is_tree, initialized;
vector<int> colors;

constexpr bool pattern[6] = {0, 0, 1, 1, 0, 1};

void Init(int a, int b)
{
    colors.clear();
    is_tree = a == 2;
    initialized = 0;
}

int Move(vector<int> y)
{
    if (!is_tree)
    {
        if (!colors.empty())
            y[colors.back()]++;

        if ((bool)y[0] + (bool)y[1] + (bool)y[2] == 1)
        {
            if (y[0])
            {
                colors.push_back(0);
                return 0;
            }
            else if (y[1])
            {
                colors.push_back(1);
                return 1;
            }
            else
            {
                colors.push_back(2);
                return 2;
            }
        }

        if (!y[0])
        {
            colors.push_back(1);
            return 1;
        }
        else if (!y[1])
        {
            colors.push_back(2);
            return 2;
        }
        else
        {
            colors.push_back(0);
            return 0;
        }
    }
    else
    {
        if (colors.empty() && y[0] + y[1] >= 3)
        {
            initialized = 1;
            if (y[0] == 1)
            {
                colors.push_back(0);
                return 0;
            }
            else
            {
                colors.push_back(1);
                return 1;
            }
        }
        if (colors.empty() && y[0] + y[1] == 1)
        {
            initialized = 1;
            colors.push_back(y[1]);
            return y[1];
        }
        if (!initialized)
        {
            if (!colors.empty() && y[0] + y[1] >= 2)
            {
                initialized = 1;
                if (!y[colors.back()])
                    return -1;
                else
                {
                    colors.push_back(!colors.back());
                    return colors.back();
                }
            }
            else
            {
                if (!(y[0] + y[1]))
                {
                    initialized = 1;
                    return -1;
                }
                if (colors.size() == 4)
                {
                    initialized = 1;
                    for (size_t i = 0; i < 6; ++i) /*  pattern */
                    {
                        bool correct = 1;
                        for (size_t j = 0; j < 4; ++j)
                            correct &= colors[j] == pattern[(i + j) % 6];
                        if (correct)
                            return -1;
                    }
                    for (size_t i = 0; i < 6; ++i) /* inverted pattern */
                    {
                        bool correct = 1;
                        for (size_t j = 0; j < 4; ++j)
                            correct &= colors[j] == !pattern[(i + j) % 6];
                        if (correct)
                            return -1;
                    }
                    return Move(y);
                }
                if (colors.empty())
                {
                    if (y[0] == 2)
                        colors.push_back(0);
                    else
                        colors.push_back(1);
                }
                if (y[0])
                {
                    colors.push_back(0);
                    return 0;
                }
                else
                {
                    colors.push_back(1);
                    return 1;
                }
            }
        }
        else
        {
            if (y[0] + y[1] >= 2)
            {
                colors.push_back(!colors.back());
                return colors.back();
            }
            colors.push_back(y[1]);
            return y[1];
        }
    }
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:10:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
Anthony.cpp:45:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
Anthony.cpp:50:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 15152 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 28 ms 14484 KB Output is correct
4 Correct 43 ms 16188 KB Output is correct
5 Correct 48 ms 16268 KB Output is correct
6 Correct 38 ms 14892 KB Output is correct
7 Correct 37 ms 14904 KB Output is correct
8 Correct 40 ms 15604 KB Output is correct
9 Correct 44 ms 15512 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 15152 KB Output is correct
2 Correct 1 ms 636 KB Output is correct
3 Correct 28 ms 14484 KB Output is correct
4 Correct 43 ms 16188 KB Output is correct
5 Correct 48 ms 16268 KB Output is correct
6 Correct 38 ms 14892 KB Output is correct
7 Correct 37 ms 14904 KB Output is correct
8 Correct 40 ms 15604 KB Output is correct
9 Correct 44 ms 15512 KB Output is correct
10 Correct 31 ms 12740 KB Output is correct
11 Correct 32 ms 12860 KB Output is correct
12 Correct 32 ms 12756 KB Output is correct
13 Correct 31 ms 12900 KB Output is correct
14 Correct 34 ms 13160 KB Output is correct
15 Correct 38 ms 13524 KB Output is correct
16 Correct 46 ms 15692 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 12696 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 28 ms 12284 KB Output is correct
4 Correct 43 ms 14044 KB Output is correct
5 Correct 44 ms 13976 KB Output is correct
6 Correct 33 ms 12620 KB Output is correct
7 Correct 32 ms 12652 KB Output is correct
8 Correct 39 ms 13340 KB Output is correct
9 Correct 38 ms 13412 KB Output is correct
10 Correct 44 ms 12988 KB Output is correct
11 Correct 40 ms 13128 KB Output is correct
12 Correct 36 ms 13160 KB Output is correct
13 Correct 37 ms 13144 KB Output is correct
14 Correct 39 ms 13372 KB Output is correct
15 Correct 46 ms 13400 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 12696 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 28 ms 12284 KB Output is correct
4 Correct 43 ms 14044 KB Output is correct
5 Correct 44 ms 13976 KB Output is correct
6 Correct 33 ms 12620 KB Output is correct
7 Correct 32 ms 12652 KB Output is correct
8 Correct 39 ms 13340 KB Output is correct
9 Correct 38 ms 13412 KB Output is correct
10 Correct 44 ms 12988 KB Output is correct
11 Correct 40 ms 13128 KB Output is correct
12 Correct 36 ms 13160 KB Output is correct
13 Correct 37 ms 13144 KB Output is correct
14 Correct 39 ms 13372 KB Output is correct
15 Correct 46 ms 13400 KB Output is correct
16 Correct 30 ms 11096 KB Output is correct
17 Correct 28 ms 10968 KB Output is correct
18 Correct 30 ms 10964 KB Output is correct
19 Correct 30 ms 10976 KB Output is correct
20 Correct 34 ms 11636 KB Output is correct
21 Correct 34 ms 11308 KB Output is correct
22 Correct 39 ms 13464 KB Output is correct
23 Correct 30 ms 11084 KB Output is correct
24 Correct 30 ms 11084 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Incorrect 2 ms 896 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 10868 KB Output is correct
2 Correct 33 ms 11240 KB Output is correct
3 Correct 0 ms 612 KB Output is correct
4 Correct 30 ms 11020 KB Output is correct
5 Correct 39 ms 12496 KB Output is correct
6 Correct 53 ms 12544 KB Output is correct
7 Incorrect 28 ms 11564 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 10776 KB Output is correct
2 Correct 34 ms 11560 KB Output is correct
3 Correct 0 ms 612 KB Output is correct
4 Correct 26 ms 11132 KB Output is correct
5 Correct 47 ms 12552 KB Output is correct
6 Correct 44 ms 12548 KB Output is correct
7 Incorrect 28 ms 11576 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -