Submission #925444

#	Time	Username	Problem	Language	Result	Execution time	Memory
925444		adaawf	Stray Cat (JOI20_stray)	C++14	15 / 100	3056 ms	22400 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> g[200005];
int f[200005], dx[] = {1, 0, 1, 0, 0, 1}, dd[200005];
vector<int> res;
void dfs(int x, int p) {
    int c = 0;
    for (auto w : g[x]) {
        if (w.second == p) continue;
        c++;
        if (c == 1) {
            for (auto w : g[x]) {
                if (w.second == p) continue;
                res[w.second] = dx[f[x]];
                f[w.first] = (f[x] + 1) % 6;
                dfs(w.first, w.second);
            }
        }
        else {
            for (auto w : g[x]) {
                if (w.second == p) continue;
                if (p == -1) res[w.second] = 0;
                else res[w.second] = res[p] ^ 1;
                if (res[w.second] == 1) f[w.first] = 1;
                else f[w.first] = 2;
                dfs(w.first, w.second);
            }
        }
    }
}
void bfs() {
    queue<int> q;
    q.push(0);
    memset(dd, 0, sizeof dd);
    dd[0] = 1;
    int d = 0;
    while (!q.empty()) {
        int h = q.size();
        for (int i = 0; i < h; i++) {
            int p = q.front();
            q.pop();
            f[p] = d;
            for (auto w : g[p]) {
                if (dd[w.first] == 0) {
                    dd[w.first] = 1;
                    q.push(w.first);
                }
            }
        }
        d++;
    }
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
	res.resize(M);
	for (int i = 0; i < M; i++) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	if (A == 2) {
		for (int i = 0; i < N; i++) f[i] = 0;
		dfs(0, -1);
	}
	else {
		bfs();
		for (int i = 0; i < M; i++) {
			res[i] = min(f[U[i]], f[V[i]]) % 3;
		}
	}
	return res;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, s = 1, flag = 0, k = 0, c = 0;
int dd[1005];
vector<int> v(5, 0);
void Init(int a, int b) {
    A = a;
    B = b;
}
int Move(vector<int> y) {
    dd[5] = dd[18] = dd[25] = dd[12] = dd[22] = dd[11] = 1;
  	if (A == 2) {
		if (s != 0) {
			s = 0;
			if (y[0] + y[1] != 2) {
				if (min(y[0], y[1]) == 0) {
                    if (y[0] < y[1]) k = 1;
                    else k = 0;
				}
				else {
                    if (y[0] > y[1]) k = 1;
                    else k = 0;
				}
				return k;
			}
			else {
				flag = 1;
                if (y[0] < y[1]) k = 1;
                else k = 0;
				y[k]--;
                if (y[0] < y[1]) v[c++] = 1;
                else v[c++] = 0;
				v[c++] = k;
				return k;
			}
		}
		else {
			if (flag == 0) {
				if (min(y[0], y[1]) == 0) {
                    if (y[0] < y[1]) k = 1;
                    else k = 0;
				}
				else k ^= 1;
				return k;
			}
			else {
				if (y[0] + y[1] != 1) {
					flag = c = 0;
					if (min(y[0], y[1]) == 0) return -1;
                    k ^= 1;
                    return k;
				}
                if (y[0] < y[1]) k = 1;
                else k = 0;
                v[c++] = k;
                if (c == 5) {
                    flag = 0;
                    int d = 0;
                    for (int i = 0; i < 5; i++) d += v[i] * (1 << i);
                    if (dd[d] == 0) {
                        return k;
                    }
                    k = v[3];
                    return -1;
                }
                return k;
			}
		}
  	}
	else {
		vector<int> v;
		for (int i = 0; i < 3; i++) {
            if (y[i] != 0) {
                v.push_back(i);
            }
		}
		if (v.size() == 1) {
            return v[0];
		}
        if (v[0] == 0) {
            if (v[1] == 1) return 0;
            return 2;
        }
        return 1;
	}
}

• 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