oj.uz

Submission #747829

# Submission time Handle Problem Language Result Execution time Memory
747829 2023-05-24T21:08:07 Z finn__ Stray Cat (JOI20_stray) C++17
15 / 100
 49 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);
    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;
                else
                    pattern_index[y] = pattern[pattern_index[x]] ? 0 : 2;
            }
    }

    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]]];
        }
    }

    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;
                    }
                    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:38:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~
Anthony.cpp:43:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         for (size_t i = 0; i < m; ++i)
      |                            ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15044 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 30 ms 14404 KB Output is correct
4 Correct 47 ms 16224 KB Output is correct
5 Correct 46 ms 16160 KB Output is correct
6 Correct 34 ms 14828 KB Output is correct
7 Correct 35 ms 15012 KB Output is correct
8 Correct 41 ms 15664 KB Output is correct
9 Correct 45 ms 15584 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15044 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 30 ms 14404 KB Output is correct
4 Correct 47 ms 16224 KB Output is correct
5 Correct 46 ms 16160 KB Output is correct
6 Correct 34 ms 14828 KB Output is correct
7 Correct 35 ms 15012 KB Output is correct
8 Correct 41 ms 15664 KB Output is correct
9 Correct 45 ms 15584 KB Output is correct
10 Correct 34 ms 12756 KB Output is correct
11 Correct 35 ms 12880 KB Output is correct
12 Correct 33 ms 12932 KB Output is correct
13 Correct 36 ms 12852 KB Output is correct
14 Correct 33 ms 13104 KB Output is correct
15 Correct 37 ms 13516 KB Output is correct
16 Correct 41 ms 15644 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12604 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 28 ms 12168 KB Output is correct
4 Correct 41 ms 13988 KB Output is correct
5 Correct 41 ms 14136 KB Output is correct
6 Correct 33 ms 12648 KB Output is correct
7 Correct 32 ms 12644 KB Output is correct
8 Correct 38 ms 13304 KB Output is correct
9 Correct 39 ms 13436 KB Output is correct
10 Correct 38 ms 13156 KB Output is correct
11 Correct 41 ms 13092 KB Output is correct
12 Correct 37 ms 13136 KB Output is correct
13 Correct 36 ms 13032 KB Output is correct
14 Correct 39 ms 13364 KB Output is correct
15 Correct 39 ms 13388 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12604 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 28 ms 12168 KB Output is correct
4 Correct 41 ms 13988 KB Output is correct
5 Correct 41 ms 14136 KB Output is correct
6 Correct 33 ms 12648 KB Output is correct
7 Correct 32 ms 12644 KB Output is correct
8 Correct 38 ms 13304 KB Output is correct
9 Correct 39 ms 13436 KB Output is correct
10 Correct 38 ms 13156 KB Output is correct
11 Correct 41 ms 13092 KB Output is correct
12 Correct 37 ms 13136 KB Output is correct
13 Correct 36 ms 13032 KB Output is correct
14 Correct 39 ms 13364 KB Output is correct
15 Correct 39 ms 13388 KB Output is correct
16 Correct 28 ms 11124 KB Output is correct
17 Correct 33 ms 11040 KB Output is correct
18 Correct 32 ms 10924 KB Output is correct
19 Correct 31 ms 10876 KB Output is correct
20 Correct 34 ms 11604 KB Output is correct
21 Correct 33 ms 11424 KB Output is correct
22 Correct 39 ms 13532 KB Output is correct
23 Correct 32 ms 11064 KB Output is correct
24 Correct 39 ms 11052 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 516 KB Output is correct
3 Correct 2 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 1 ms 892 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 900 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Incorrect 2 ms 904 KB Wrong Answer [5]
11 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10548 KB Output is correct
2 Correct 37 ms 11036 KB Output is correct
3 Correct 0 ms 508 KB Output is correct
4 Correct 27 ms 10712 KB Output is correct
5 Correct 41 ms 12008 KB Output is correct
6 Correct 40 ms 12112 KB Output is correct
7 Correct 34 ms 11072 KB Output is correct
8 Incorrect 32 ms 11128 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10728 KB Output is correct
2 Correct 33 ms 10952 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 28 ms 10668 KB Output is correct
5 Correct 45 ms 12056 KB Output is correct
6 Correct 39 ms 12096 KB Output is correct
7 Correct 35 ms 11028 KB Output is correct
8 Incorrect 30 ms 11180 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -