oj.uz

Submission #747826

# Submission time Handle Problem Language Result Execution time Memory
747826 2023-05-24T20:57:55 Z finn__ Stray Cat (JOI20_stray) C++17
15 / 100
 47 ms 16224 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
                    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

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15004 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 14488 KB Output is correct
4 Correct 45 ms 16136 KB Output is correct
5 Correct 45 ms 16224 KB Output is correct
6 Correct 38 ms 14760 KB Output is correct
7 Correct 35 ms 14792 KB Output is correct
8 Correct 40 ms 15744 KB Output is correct
9 Correct 47 ms 15560 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15004 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 30 ms 14488 KB Output is correct
4 Correct 45 ms 16136 KB Output is correct
5 Correct 45 ms 16224 KB Output is correct
6 Correct 38 ms 14760 KB Output is correct
7 Correct 35 ms 14792 KB Output is correct
8 Correct 40 ms 15744 KB Output is correct
9 Correct 47 ms 15560 KB Output is correct
10 Correct 33 ms 12856 KB Output is correct
11 Correct 31 ms 12756 KB Output is correct
12 Correct 35 ms 12924 KB Output is correct
13 Correct 33 ms 12832 KB Output is correct
14 Correct 35 ms 13164 KB Output is correct
15 Correct 40 ms 13528 KB Output is correct
16 Correct 40 ms 15816 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12652 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 27 ms 12252 KB Output is correct
4 Correct 41 ms 14008 KB Output is correct
5 Correct 43 ms 14012 KB Output is correct
6 Correct 34 ms 12636 KB Output is correct
7 Correct 32 ms 12652 KB Output is correct
8 Correct 37 ms 13416 KB Output is correct
9 Correct 42 ms 13348 KB Output is correct
10 Correct 37 ms 13048 KB Output is correct
11 Correct 37 ms 13128 KB Output is correct
12 Correct 39 ms 13036 KB Output is correct
13 Correct 39 ms 12988 KB Output is correct
14 Correct 40 ms 13468 KB Output is correct
15 Correct 38 ms 13300 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12652 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 27 ms 12252 KB Output is correct
4 Correct 41 ms 14008 KB Output is correct
5 Correct 43 ms 14012 KB Output is correct
6 Correct 34 ms 12636 KB Output is correct
7 Correct 32 ms 12652 KB Output is correct
8 Correct 37 ms 13416 KB Output is correct
9 Correct 42 ms 13348 KB Output is correct
10 Correct 37 ms 13048 KB Output is correct
11 Correct 37 ms 13128 KB Output is correct
12 Correct 39 ms 13036 KB Output is correct
13 Correct 39 ms 12988 KB Output is correct
14 Correct 40 ms 13468 KB Output is correct
15 Correct 38 ms 13300 KB Output is correct
16 Correct 28 ms 11116 KB Output is correct
17 Correct 28 ms 11116 KB Output is correct
18 Correct 31 ms 11024 KB Output is correct
19 Correct 30 ms 10984 KB Output is correct
20 Correct 38 ms 11492 KB Output is correct
21 Correct 32 ms 11360 KB Output is correct
22 Correct 38 ms 13552 KB Output is correct
23 Correct 31 ms 11116 KB Output is correct
24 Correct 31 ms 11088 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 504 KB Output is correct
3 Correct 2 ms 900 KB Output is correct
4 Correct 3 ms 908 KB Output is correct
5 Correct 2 ms 908 KB Output is correct
6 Correct 2 ms 908 KB Output is correct
7 Incorrect 2 ms 908 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10800 KB Output is correct
2 Incorrect 28 ms 11304 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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