| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 955427 | abczz | Stray Cat (JOI20_stray) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (x == 2 || x == 3 || x == 5) E[x] = w;
else E[x] = w^1;
solve(v, u, E[x], (x+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;
}
#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, lazy;
bool isinitSame;
void Init(int A, int B) {
if (!B) mode = 0;
else mode = 1;
}
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) {
if (rev) {
--rev;
return -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;
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;
return -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 (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;
}
}
if ((y[0])) {
V.push_back(0);
return p = 0;
}
else {
V.push_back(1);
return p = 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 = -2;
return -1;
}
else {
dir = 1e18;
if (y[0]) return p = 0;
else return p = 1;
}
}
else if (dir == -2) {
dir = 1e18;
if (y[0]) return p = 0;
else return p = 1;
}
}
return -2;
}
}
int Move(std::vector<int> y) {
if (!mode) return CmodeA(y);
else return CmodeB(y);
}