Submission #1280706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280706		avighna	길고양이 (JOI20_stray)	C++20	5 / 100	38 ms	12492 KiB

Anthony

#include "Anthony.h"
#include <queue>
#include <string>
#include <vector>

namespace {

std::string s = "110100";

}

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
  std::vector<std::vector<std::pair<int, int>>> adj(N);
  for (int i = 0; i < M; ++i) {
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }

  std::vector<int> ans(M);
  auto dfs = [&](auto &&self, int u, int p, int c, int st) -> void {
    if (adj[u].size() != 2) { // if we're not a degree 2, make sure to color alternatingly
      if (st != -1) {
        st = -1;
      }
      for (auto &[i, edge_idx] : adj[u]) {
        if (i == p) {
          continue;
        }
        ans[edge_idx] = c;
        self(self, i, u, !ans[edge_idx], st);
      }
      return;
    }
    if (st == -1) {
      st = s.find(!c + '0') + 1;
    }
    st = st % s.length();
    for (auto &[i, edge_idx] : adj[u]) { // should only run for one node cuz we skip parent
      if (i == p) {
        continue;
      }
      ans[edge_idx] = s[st] - '0';
      self(self, i, u, !ans[edge_idx], st + 1);
    }
  };
  dfs(dfs, 0, -1, 0, -1);

  return ans;
}

Catherine

#include "Catherine.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>

namespace {

int A, B;

std::string corr = "110100";
std::vector<std::string> poss;
int prev = -1;
bool fixed = false;
std::string picked;

} // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  for (int i = 0; i < 6; ++i) {
    std::string t;
    for (int j = 0; j < 5; ++j) {
      t.push_back(corr[(i + j) % 6]);
    }
    poss.push_back(t);
  }
}

int Move(std::vector<int> y) {
  auto pick = [&](int x) {
    picked.push_back((prev = x == -1 ? prev : x) + '0');
    return x == -1 ? x : prev;
  };
  int z = y[0] + (prev == 0), o = y[1] + (prev == 1);
  // if we're at a leaf then just return -1 and claim fixed
  if (y[0] == 0 and y[1] == 0) {
    fixed = true;
    return pick(-1);
  }
  // we're guranteed o+z != 0
  auto minority = [&]() {
    if (o < z) {
      return (o - (prev == 1)) ? 1 : -1;
    }
    return (z - (prev == 0)) ? 0 : -1;
  };
  // if we can, choose minority
  if (z != o and o != 0 and z != 0) {
    fixed = true;
    return pick(minority());
  }

  // now we're sure all counts are equal
  // so we're at a deg=2

  // but if we're already fixed, we can just pick the only (parent) edge
  if (fixed) {
    return pick((o - (prev == 1)) > (z - (prev == 0)));
  }

  // not fixed and deg 2
  // so we either fix it the next time we land up here or it fixes itself by encountering deg!=2

  // fix it
  if (picked.length() == 5) {
    fixed = true;
    auto it = std::find(poss.begin(), poss.end(), picked);
    if (it != poss.end()) { // we're going away from the root
      return pick(-1);
    }
  }

  if (prev == -1) {
    // steal extra entropy
    if (o == 0) {
      picked.push_back('0');
    } else if (z == 0) {
      picked.push_back('1');
    } else {
      picked.push_back((o < z) + '0');
    }
  }

  return pick((o - (prev == 1)) > (z - (prev == 0))); // either fixed pick, so its fine, or random pick if prev is -1
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 71
• Subtask 7: 0 / 9