oj.uz

Submission #802670

# Submission time Handle Problem Language Result Execution time Memory
802670 2023-08-02T13:15:44 Z Um_nik Stray Cat (JOI20_stray) C++17
20 / 100
 47 ms 16784 KB 
#include "Anthony.h"
#include <vector>
#include <cassert>
using namespace std;

using pii = pair<int, int>;

namespace {

}  // namespace

vector<int> Mark(int N, int M, int A, int B,
                      vector<int> U, vector<int> V) {
  vector<int> X(M, -1);
  vector<vector<pii>> g(N, vector<pii>());
  for (int i = 0; i < M; i++) {
    int u = U[i], v = V[i];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  vector<int> dist(N, N);
  dist[0] = 0;
  vector<int> q;
  q.push_back(0);
  for (int i = 0; i < (int)q.size(); i++) {
    int v = q[i];
    for (pii e : g[v]) if (dist[e.first] == N) {
      dist[e.first] = dist[v] + 1;
      q.push_back(e.first);
    }
  }
  assert((int)q.size() == N);

  if (A >= 3) {
    for (int i = 0; i < M; i++)
      X[i] = min(dist[U[i]], dist[V[i]]) % 3;
  } else {
    assert(M == N - 1);
    vector<int> posInBamboo(N, -1);
    for (int i = 0; i < N; i++) {
      int v = q[i];
      if (i == 0) {
        for (auto [u, id] : g[v]) {
          X[id] = 0;
        }
        continue;
      }
      int deg = (int)g[v].size();
      if (deg == 1) continue;
      int par = -1;
      int parC = -1;
      for (auto [u, id] : g[v]) if (dist[u] < dist[v]) {
        par = u;
        parC = X[id];
      }
      if (deg == 2) {
        if (posInBamboo[par] != -1) {
          posInBamboo[v] = (posInBamboo[par] + 1) % 6;
        } else {
          posInBamboo[v] = parC + 1;
        }
        int col = (posInBamboo[v] == 0 || posInBamboo[v] == 2 || posInBamboo[v] == 3 ? 0 : 1);
        for (auto [u, id] : g[v]) if (u != par)
          X[id] = col;
      } else {
        for (auto [u, id] : g[v]) if (u != par)
          X[id] = parC ^ 1;
      }
    }
  }
  return X;
}

#include "Catherine.h"
#include <vector>
#include <cassert>
using namespace std;

namespace {

int A;
bool bambooPart;
vector<int> colors;

bool GoingUp(vector<int> s) {
  vector<int> t = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};
  for (int i = 0; i + (int)s.size() <= (int)t.size(); i++) {
    bool ok = true;
    for (int j = 0; j < (int)s.size(); j++)
      ok &= s[j] == t[i + j];
    if (ok) return true;
  }
  return false;
}

}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::bambooPart = true;
  ::colors = vector<int>();
}

int Move(std::vector<int> y) {
  if (::A > 2) {
    int c = 0;
    while(c < 3) {
      if (y[c] > 0 && y[(c + 2) % 3] == 0) break;
      c++;
    }
    assert(c < 3);
    return c;
  } else {
    if (!::colors.empty()) y[::colors.back()]++;
    int deg = y[0] + y[1];
    int col = -2;
    if (deg == 1) {
      ::bambooPart = false;
      if (::colors.empty()) {
        col = (y[0] > 0 ? 0 : 1);
      } else {
        col = -1;
      }
    } else if (deg == 2) {
      if (!::bambooPart) {
        assert(!::colors.empty());
        y[::colors.back()]--;
        col = (y[0] > 0 ? 0 : 1);
      } else {
        if ((int)::colors.size() < 3) {
          if (!::colors.empty()) y[::colors.back()]--;
          col = (y[0] > 0 ? 0 : 1);
        } else {
          y[::colors.back()]--;
          col = (y[0] > 0 ? 0 : 1);
          vector<int> s = ::colors;
          s.push_back(col);
          if (!::GoingUp(s)) col = -1;
          ::bambooPart = false;
        }
      }
    } else {
      assert(deg > 2);
      ::bambooPart = false;
      col = (y[0] == 1 ? 0 : 1);
      assert(y[col] == 1);
      if (!::colors.empty() && ::colors.back() == col) col = -1;
    }
    if (col == -1) {
      int x = ::colors.back();
      ::colors.push_back(x);
    } else {
      ::colors.push_back(col);
    }
    return col;
  }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15500 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 25 ms 14856 KB Output is correct
4 Correct 34 ms 16784 KB Output is correct
5 Correct 34 ms 16680 KB Output is correct
6 Correct 27 ms 15556 KB Output is correct
7 Correct 30 ms 15572 KB Output is correct
8 Correct 46 ms 16204 KB Output is correct
9 Correct 36 ms 16264 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15500 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 25 ms 14856 KB Output is correct
4 Correct 34 ms 16784 KB Output is correct
5 Correct 34 ms 16680 KB Output is correct
6 Correct 27 ms 15556 KB Output is correct
7 Correct 30 ms 15572 KB Output is correct
8 Correct 46 ms 16204 KB Output is correct
9 Correct 36 ms 16264 KB Output is correct
10 Correct 34 ms 13340 KB Output is correct
11 Correct 29 ms 13428 KB Output is correct
12 Correct 38 ms 13508 KB Output is correct
13 Correct 36 ms 13404 KB Output is correct
14 Correct 36 ms 13732 KB Output is correct
15 Correct 30 ms 14124 KB Output is correct
16 Correct 32 ms 16308 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13112 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 24 ms 12824 KB Output is correct
4 Correct 40 ms 14556 KB Output is correct
5 Correct 46 ms 14468 KB Output is correct
6 Correct 40 ms 13256 KB Output is correct
7 Correct 40 ms 13288 KB Output is correct
8 Correct 47 ms 13860 KB Output is correct
9 Correct 32 ms 13928 KB Output is correct
10 Correct 31 ms 13632 KB Output is correct
11 Correct 32 ms 13672 KB Output is correct
12 Correct 36 ms 13652 KB Output is correct
13 Correct 40 ms 13648 KB Output is correct
14 Correct 44 ms 13860 KB Output is correct
15 Correct 36 ms 13952 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13112 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 24 ms 12824 KB Output is correct
4 Correct 40 ms 14556 KB Output is correct
5 Correct 46 ms 14468 KB Output is correct
6 Correct 40 ms 13256 KB Output is correct
7 Correct 40 ms 13288 KB Output is correct
8 Correct 47 ms 13860 KB Output is correct
9 Correct 32 ms 13928 KB Output is correct
10 Correct 31 ms 13632 KB Output is correct
11 Correct 32 ms 13672 KB Output is correct
12 Correct 36 ms 13652 KB Output is correct
13 Correct 40 ms 13648 KB Output is correct
14 Correct 44 ms 13860 KB Output is correct
15 Correct 36 ms 13952 KB Output is correct
16 Correct 36 ms 11580 KB Output is correct
17 Correct 23 ms 11676 KB Output is correct
18 Correct 31 ms 11752 KB Output is correct
19 Correct 35 ms 11476 KB Output is correct
20 Correct 30 ms 12196 KB Output is correct
21 Correct 27 ms 11860 KB Output is correct
22 Correct 36 ms 14080 KB Output is correct
23 Correct 27 ms 11752 KB Output is correct
24 Correct 25 ms 11752 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Correct 0 ms 592 KB Output is correct
3 Correct 2 ms 892 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 1 ms 784 KB Output is correct
6 Correct 2 ms 772 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 780 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 900 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 1 ms 780 KB Output is correct
15 Correct 1 ms 772 KB Output is correct
16 Correct 2 ms 900 KB Output is correct
17 Correct 1 ms 908 KB Output is correct
18 Correct 1 ms 900 KB Output is correct
19 Correct 2 ms 900 KB Output is correct
20 Correct 2 ms 780 KB Output is correct
21 Correct 2 ms 916 KB Output is correct
22 Correct 2 ms 772 KB Output is correct
23 Correct 2 ms 908 KB Output is correct
24 Correct 1 ms 908 KB Output is correct
25 Correct 2 ms 848 KB Output is correct
26 Correct 2 ms 772 KB Output is correct
27 Correct 1 ms 904 KB Output is correct
28 Correct 2 ms 772 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11396 KB Output is correct
2 Correct 27 ms 11880 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 11084 KB Output is correct
5 Correct 31 ms 12656 KB Output is correct
6 Correct 30 ms 12744 KB Output is correct
7 Correct 26 ms 11716 KB Output is correct
8 Correct 26 ms 11732 KB Output is correct
9 Correct 31 ms 12564 KB Output is correct
10 Correct 34 ms 12736 KB Output is correct
11 Correct 30 ms 12712 KB Output is correct
12 Correct 31 ms 12776 KB Output is correct
13 Correct 31 ms 12692 KB Output is correct
14 Correct 33 ms 12744 KB Output is correct
15 Correct 36 ms 12628 KB Output is correct
16 Correct 33 ms 12716 KB Output is correct
17 Correct 28 ms 12368 KB Output is correct
18 Correct 27 ms 12448 KB Output is correct
19 Incorrect 34 ms 12232 KB Wrong Answer [6]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11392 KB Output is correct
2 Correct 35 ms 11780 KB Output is correct
3 Correct 0 ms 524 KB Output is correct
4 Correct 26 ms 11248 KB Output is correct
5 Correct 34 ms 12584 KB Output is correct
6 Correct 38 ms 12672 KB Output is correct
7 Correct 35 ms 11644 KB Output is correct
8 Correct 31 ms 11592 KB Output is correct
9 Correct 31 ms 12696 KB Output is correct
10 Correct 31 ms 12712 KB Output is correct
11 Correct 43 ms 12784 KB Output is correct
12 Correct 35 ms 12588 KB Output is correct
13 Correct 32 ms 12712 KB Output is correct
14 Correct 34 ms 12720 KB Output is correct
15 Incorrect 28 ms 12688 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -