Submission #955467

#	Time	Username	Problem	Language	Result	Execution time	Memory
955467		abczz	Stray Cat (JOI20_stray)	C++14	100 / 100	39 ms	17192 KiB

Anthony

#include "Anthony.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define ll long long
using namespace std;

namespace {
  queue <array<ll, 2>> Q;
  bool visited[20000], heavy[20000];
  vector <int> E;
  vector <array<ll, 2>> adj[20000];

  void AmodeA() {
    Q.push({0, 0});
    while (!Q.empty()) {
      auto [u, w] = Q.front();
      Q.pop();
      for (auto [v, x] : adj[u]) {
        if (E[x] == -1) E[x] = w;
        if (!visited[v]) {
          visited[v] = 1;
          Q.push({v, (w+1) % 3});
        }
      }
    }
  }

  void dfs(ll u, ll p) {
    ll chd_cnt = 0;
    for (auto [v, x] : adj[u]) {
      if (v != p) {
        ++chd_cnt;
        dfs(v, u);
      }
    }
    if (chd_cnt != 1 || p == -1) heavy[u] = 1;
  }

  void solve(ll u, ll p, ll w, ll z) {
    for (auto [v, x] : adj[u]) {
      if (v != p) {
        if (heavy[u] && heavy[v]) {
          E[x] = w^1;
          solve(v, u, E[x], 0);
        }
        else if (heavy[u] && !heavy[v]) {
          E[x] = w^1;
          solve(v, u, E[x], 1);
        }
        else {
          if (z == 2 || z == 4 || z == 5) E[x] = w;
          else E[x] = w^1;
          solve(v, u, E[x], (z+1) % 6);
        }
      }
    }
  }

  void AmodeB() {
    dfs(0, -1);
    solve(0, -1, 1, 0);
  }
}

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  E.resize(M);
  for (int i=0; i<M; ++i) {
    E[i] = -1;
    adj[U[i]].push_back({V[i], i});
    adj[V[i]].push_back({U[i], i});
  }
  if (!B) AmodeA();
  else AmodeB();
  return E;
}

Catherine

#include "Catherine.h"
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
 
namespace {
  bool mode;
  vector <ll> V;
  ll p = -1, dir = -1, x = 0, rev = 0, l = 1e18, r = 1e18;
  bool isinitSame;
 
  int CmodeA(vector <int> y) {
    ll cnt = 0, id;
    for (int i=0; i<3; ++i) {
      if (y[i] > 0) {
        ++cnt;
        id = i;
      }
    }
    if (cnt == 1) return id;
    if (y[0] && y[1]) return 0;
    else if (y[0] && y[2]) return 2;
    else return 1;
  }
 
  int CmodeB(vector <int> y) {
    if (dir == 1e18) {
      if (!y[0]) return p = 1;
      else if (!y[1]) return p = 0;
      p ^= 1;
      return p;
    }
    else if (dir == -1) {
      if (!y[0] && y[1] == 1) {
        dir = 1e18;
        return p = 1;
      }
      else if (y[0] == 1 && !y[1]) {
        dir = 1e18;
        return p = 0;
      }
      if (y[0] == 1 && y[1] > 1) {
        dir = 1e18;
        return p = 0;
      }
      else if (y[0] > 1 && y[1] == 1) {
        dir = 1e18;
        return p = 1;
      }
      dir = 0;
      if (!y[0] || !y[1]) {
        isinitSame = 1;
        if (y[0]) return p = 0;
        else return p = 1;
      }
      else {
        x = 1;
        return p = 0;
      }
    }
    if (!y[0] && !y[1]) {
      dir = 1e18;
      return -1;
    }
    else if (min(y[0], y[1]) == 0 && max(y[0], y[1]) > 1) {
      dir = 1e18;
      return -1;
    }
    else if (min(y[0], y[1]) >= 1) {
      dir = 1e18;
      p ^= 1;
      return p;
    }
    if (!isinitSame) {
      //cout << l << " " << r << " " << x << " " << rev << endl;
      if (rev) {
        --rev;
        if (y[0]) return p = 0;
        else return p = 1;
      }
      else if (l == 1e18) {
        if (y[0]) {
          if (x == 2) {
            l = 3;
            rev = 1, x = 0;
            return -1;
          }
          else {
            ++x;
            return p = 0;
          }
        }
        else {
          l = x;
          if (x == 2) rev = 1;
          x = 0;
          return -1;
        }
      }
      else if (r == 1e18) {
        if (y[1]) {
          ++x;
          if (x == 1) return p = 1;
          else if (x == 2) {
            if (l >= 2) {
              r = 2;
              return -1;
            }
            else {
              ++x;
              return p = 1;
            }
          }
          else {
            r = 3;
            rev = 1;
            return -1;
          }
        }
        else {
          r = x;
          if (x == 2) rev = 1;
          return -1;
        }
      }
      else {
        if (l == r) ++r;
        if ((l == 1 && r == 2) || (l == 2 && r == 3) || (l == 3 && r == 1)) {
          dir = 1e18;
          p = 0;
          if (y[0]) return 0;
          else return -1;
        }
        else {
          dir = 1e18;
          p = 1;
          if (y[1]) return 1;
          else return -1;
        }
      }
    }
    else {
      if (rev) {
        --rev;
        if (y[0]) return p = 0;
        else return p = 1;
      }
      else if (dir == 0) {
        if ((y[0] && !p) || (y[1] && p)) {
          dir = 1;
          return p;
        }
        else {
          dir = 2;
          if (y[0]) return p = 0;
          else return p = 1;
        }
      }
      else if (dir == 1) {
        if (y[0]) {
          V.push_back(0);
          if (V.size() == 1) return p = 0;
        }
        else {
          V.push_back(1);
          if (V.size() == 1) return p = 1;
        }
        if (V.size() == 2) {
          if (V[0] == V[1]) {
            dir = 1e18;
            if (y[0]) return p = 0;
            else return p = 1;
          }
          else {
            dir = -2;
            rev = 2;
            return -1;
          }
        }
      }
      else if (dir == 2) {
        if ((y[0] && !p) || (y[1] && p)) {
          dir = 3;
          return p;
        }
        else {
          dir = 4;
          rev = 1;
          return -1;
        }
      }
      else if (dir == 3) {
        if ((y[0] && !p) || (y[1] && p)) {
          dir = -2;
          rev = 2;
          return -1;
        }
        else {
          dir = 1e18;
          if (y[0]) return p = 0;
          else return p = 1;
        }
      }
      else if (dir == 4) {
        dir = 5;
        if (y[0]) return p = 0;
        else return p = 1;
      }
      else if (dir == 5) {
        if ((y[0] && !p) || (y[1] && p)) {
          dir = 1e18;
          if (y[0]) return p = 0;
          else return p = 1;
        }
        else {
          dir = -2;
          return -1;
        }
      }
      else if (dir == -2) {
        dir = 1e18;
        if (y[0]) return p = 0;
        else return p = 1;
      }
    }
    return -2;
  }
}
 
void Init(int A, int B) {
  if (!B) mode = 0;
  else mode = 1;
}
 
int Move(std::vector<int> y) {
  if (!mode) return CmodeA(y);
  else return CmodeB(y);
}

Compilation message (stderr)

Anthony.cpp: In function 'void {anonymous}::AmodeA()':
Anthony.cpp:18:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |       auto [u, w] = Q.front();
      |            ^
Anthony.cpp:20:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |       for (auto [v, x] : adj[u]) {
      |                 ^
Anthony.cpp: In function 'void {anonymous}::dfs(long long int, long long int)':
Anthony.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for (auto [v, x] : adj[u]) {
      |               ^
Anthony.cpp: In function 'void {anonymous}::solve(long long int, long long int, long long int, long long int)':
Anthony.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [v, x] : adj[u]) {
      |               ^

• 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