Submission #549882

#	Time	Username	Problem	Language	Result	Execution time	Memory
549882		jesus_coconut	Stray Cat (JOI20_stray)	C++17	100 / 100	56 ms	16460 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;


namespace {
vector<vector<int>> adj;
vector<int> dist;
void bfs() {
    queue<int> q;
    dist.resize(adj.size(), INT_MAX);
    q.push(0);
    dist[0] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
}

vector<int> s{0, 0, 1, 0, 1, 1};

vector<pair<int, int>> v;
void dfs(int ver, int par, int col, int len) {
    v[ver] = {par, col};
    int numchild = adj[ver].size() - (par != -1);
    if (numchild > 1) {
        for (auto c : adj[ver]) if (c != par) {
            dfs(c, ver, !col, -1);
        }
    } else {
        if (len == -1) {
            if (col == 0) len = 1;
            else len = 3;
        }
        for (auto c : adj[ver]) if (c != par) {
            dfs(c, ver, s[len], (len + 1) % 6);
        }
    }

}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    adj.resize(N);
    for (int i = 0; i < M; ++i) {
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
  if (A >= 3) {
        bfs();
        vector<int> ret(M);
        for (int i = 0; i < M; ++i) {
            ret[i] = min(dist[U[i]], dist[V[i]]) % 3;
        }
        return ret;
  }
  v.resize(N);
  dfs(0, -1, 0, -1);
  vector<int> ret(M);
  for (int i = 0; i < M; ++i) {
    if (v[U[i]].first == V[i]) {
        ret[i] = v[U[i]].second;
    } else {
        ret[i] = v[V[i]].second;
    }
  }
  return ret;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int A, B;
int prv;
vector<int> pat{0, 0, 1, 0, 1, 1};
vector<int> cur;
bool correct;
}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  ::prv = -1;
  ::correct = false;
}

int Move(std::vector<int> y) {
  if (A >= 3) {
    if (y[0] == 0) {
        if (y[1] == 0) return 2;
        return 1;
    } else if (y[1] == 0) {
        if (y[2] == 0) return 0;
        return 2;
    } else if (y[2] == 0) {
        if (y[0] == 0) return 1;
        return 0;
    }
    assert(false);
  }
  int cntadj = accumulate(begin(y), end(y), 0) + (prv != -1);
  if (cntadj > 2) {
    correct = true;
    if (prv != -1 && y[prv] == 0) return -1;
    if (prv != -1) y[prv]++;
    if (y[0] == 1) return prv = 0;
    else if (y[1] == 1) return prv = 1;
    assert(false);
  }
  if (cntadj == 1) {
    correct = true;
    if (prv != -1) {
        return -1;
    } else {
        if (y[0] == 1) return prv = 0;
        else if (y[1] == 1) return prv = 1;
        assert(false);
    }
  }
  if (correct) {
    if (y[0] > 0) return prv = 0;
    else if (y[1] > 0) return  prv = 1;
    assert(false);
  }
  if (prv == -1) {
    if (y[0] > 0) {
        cur.push_back(0);
        if (y[1] > 0) {
            cur.push_back(1);
            return prv = 1;
        } else {
            cur.push_back(0);
            return prv = 0;
        }
    } else {
        assert(y[1] > 0);
        cur.push_back(1);
        cur.push_back(1);
        return prv = 1;
    }
  } else {
    if (y[0] > 0) {
        cur.push_back(0);
    } else {
        assert(y[1] > 0);
        cur.push_back(1);
    }
    if (cur.size() == 5) {
        for (int i = 0; i < 10; ++i) {
            bool g = true;
            for (int j = 0; j < 5; ++j) {
                if (cur[j] != pat[(j + i) % size(pat)]) g = false;
            }
            if (g) {
                correct = true;
                return -1;
            }
        }

        correct = true;
        assert(y[cur.back()] > 0);
        return prv = cur.back();
    } else {
        assert(y[cur.back()] > 0);
        return prv = cur.back();
    }
  }
}

• 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