Submission #802693

#	Time	Username	Problem	Language	Result	Execution time	Memory
802693		Um_nik	Stray Cat (JOI20_stray)	C++17	100 / 100	57 ms	16252 KiB

Anthony

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

Catherine

#include "Catherine.h"
#include <vector>
#include <cassert>
#include <algorithm>
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};
//  reverse(t.begin(), t.end());
  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() < 4) {
          if (!::colors.empty()) y[::colors.back()]--;
          col = (y[0] > 0 ? 0 : 1);
          if (::colors.empty()) {
            y[col]--;
            ::colors.push_back((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 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9