Submission #1126368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126368		efedmrlr	Stray Cat (JOI20_stray)	C++20	15 / 100	49 ms	13896 KiB

Anthony

#include "Anthony.h"
#include <vector>
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


namespace {
  const int NMAX = 3e4+5;
  vector<vector<array<int, 2> > > adj, ch;
  queue<array<int, 3> > qu;
  vector<int> vis, p, pedg, dep;
  std::vector<int> X;
  vector<vector<int> > COLS = { {2, 0}, {0, 2}, {1, 1} }; 
  void dfs5(int node, int col) {
    
    if(node) X[pedg[node]] = col;
    col++;
    col %= 3;
    for(auto c : ch[node]) {
      dfs5(c[0], col);
    }
  }
  int get_col(int x) {
    if((int)ch[x].size() != 1) return 0;
    vector<int> cnt(2, 0);
    cnt[X[ch[x][0][1]]]++;
    cnt[X[pedg[x]]]++;
    for(int i = 0; i < 3; i++) {
      if(cnt == COLS[i]) return i;
    }
    assert(0);
  }
  void dfs(int node) {
    if(node && ch[node].size() == 1) {
      int col = get_col(p[node]);
      col++;
      col %= 3;
      auto tmp = COLS[col];
      tmp[X[pedg[node]]]--;
      for(int i = 0; i < 2; i++) {
        if(tmp[i]) {
          X[ch[node][0][1]] = i;
        }
      }
      dfs(ch[node][0][0]);
    }
    else {
      for(auto c : ch[node]) {
        X[c[1]] = !X[pedg[node]];
        if(!node) X[c[1]] = 0;
        dfs(c[0]);
      }
    }
  }
}  // namespace


std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  X.assign(M, -1);
  vis.assign(N + 5, 0);
  p.assign(N + 5, 0);
  dep.assign(N + 5, 0);
  pedg.assign(N + 5, 0);
  while(qu.size()) qu.pop();
  ch.assign(N + 5, vector<array<int, 2> >());
  adj.assign(N + 5, vector<array<int, 2> >());
  for(int i = 0; i < M; i++) {
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i});
  }
  qu.push({0, 0, 0});
  dep[0] = 0;
  while(qu.size()) {
    auto cur = qu.front();
    qu.pop();
    if(vis[cur[0]]) continue;
    vis[cur[0]] = 1;
    p[cur[0]] = cur[1];
    dep[cur[0]] = dep[cur[1]] + 1;
    pedg[cur[0]] = cur[2];
    for(auto c : adj[cur[0]]) {
      if(vis[c[0]]) continue;
      qu.push({c[0], cur[0], c[1]});
    }
  }
  for(int i = 1; i < N; i++) {
    ch[p[i]].pb({i, pedg[i]});
  }
  if(B == 0) {
    dfs5(0, 0);
    for(int i = 0; i < M; i++) {
      if(X[i] != -1) continue;
      if(dep[U[i]] < dep[V[i]]) swap(U[i], V[i]);
      X[i] = X[pedg[U[i]]];
      if(dep[U[i]] == dep[V[i]]) {
        X[i]++;
        X[i] %= 3;
      }
    }
  }
  else {
    dfs(0);
  }
  // cout << "edges: \n";
  // for(auto c : X) {
  //   cout << c << " ";
  // }
  // cout << "\n";
  return X;
}

Catherine

#include "Catherine.h"
#include <vector>
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

namespace {
  vector<vector<int> > COLS = { {2, 0}, {0, 2}, {1, 1} }; 
  int A, B;
  int cur_edg = -1;
  int prev_col = -1;
  bool f = 0;
  bool turn = 0;
  int beg = 0;
  void move_to(int x) {
    // cout << "move: " << beg << " moved to:" << x << endl;
    beg++;
    if(x == -1) return;
    turn = !x;
    cur_edg = x;
    return;
  }
  int get_col(vector<int> a) {
    for(int i = 0; i < 3; i++) {
      if(a == COLS[i]) return i;
    }
    assert(0);
  }
}  // namespace

void Init(int A, int B) {
  cur_edg = -1;
  beg = 0;
  prev_col = -1;
  f = 0;
  turn = 0;
  ::A = A;
  ::B = B;
}

int Move(std::vector<int> y) {
  if(B == 0) {
    for(int i = 0; i < 3; i++) {
      int nxt = i + 1;
      nxt %= 3;
      if(y[nxt] && y[i]) {
        return i;
      }
    }
    for(int i = 0; i < 3; i++) {
      if(y[i]) return i;
    }
    assert(0);
  }
  else {
    int sum = y[0] + y[1];
    if(beg) {
      sum++;
    }
    if(f) {
      if(sum == 2) {
        move_to(y[1] == 1);
        return y[1] == 1;
      }
      move_to(turn);
      return !turn;
    }
    if(sum == 1) {
      f = 1;
      if(!beg) {
        move_to(y[1] == 1);
        return y[1] == 1;
      }
      else {
        move_to(-1);
        return -1;
      }
    }
    if(sum > 2) {
        f = 1;
        if(beg) y[cur_edg]++;
        if(y[cur_edg] == 1) {
          move_to(-1);
          return -1;
        }
        else if(y[0] == 1) {
          move_to(0);
          return 0;
        }
        else {
          move_to(1);
          return 1;
        }
    }  
    if(!beg) {
        prev_col = get_col(y);
        if(y[0]) {
          move_to(0); return 0;
        }
        else {
          move_to(1); return 1;
        }
    }
    else if(beg == 1) {
      // cout << "here" << endl;
      y[cur_edg]++;
      int col = get_col(y);
      y[cur_edg]--;
      f = 1;
      if((col + 1) % 3 == prev_col) {
        move_to(y[1] == 1);
        return y[1] == 1;
      }
      else {
        move_to(-1);
        return -1;
      }
    }
    assert(0);
  }
}

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