oj.uz

Submission #212388

# Submission time Handle Problem Language Result Execution time Memory
212388 2020-03-22T20:54:10 Z JustasZ Stray Cat (JOI20_stray) C++14
15 / 100
 86 ms 17012 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e4 + 100;
const int mod = 1e9 + 7;

namespace {

	int n, m, A, B;
	vector<int>U, V, label;
	vector<pii>adj[maxn];
	
	void solve1() {
		queue<int>Q;
		vector<int>dist(n, mod);
		dist[0] = 0;
		Q.push(0);

		while (sz(Q)) {
			int v = Q.front();
			Q.pop();
			for (pii to : adj[v]) {
				if (dist[to.x] > dist[v] + 1) {
					dist[to.x] = dist[v] + 1;
					Q.push(to.x);
				}
			}
		}

		for (int i = 0; i < m; i++) {
			label[i] = min(dist[V[i]], dist[U[i]]) % 3;
		}
	}

	string s = "010011";
	void dfs(int v, int p, int prev_label) {
		for (pii to : adj[v]) {
			if (to.x != p) {
				if (sz(adj[v]) > 2) {
					int new_label = (s[prev_label] - '0') ^ 1;
					label[to.y] = new_label;
					dfs(to.x, v, new_label);
				} else {
					int new_label = (prev_label + 1) % 6;
					label[to.y] = (s[new_label] - '0');
					dfs(to.x, v, new_label);
				}
			}
		}
	}

	void solve2() {
		dfs(0, 0, 0);
	}

	vector<int> solve(int N, int M, int AA, int BB, vector<int>UU, vector<int>VV) {
		n = N, m = M, A = AA, B = BB;
		U = UU, V = VV;
		label.resize(m);
		for (int i = 0; i < m; i++) {
			adj[U[i]].pb({V[i], i});
			adj[V[i]].pb({U[i], i});
		}
		if (A >= 3) {
			solve1();
		} else {
			solve2();
		}
		return label;
	}

}  // namespace

vector<int>Mark(int N, int M, int A, int B, vector<int>U, vector<int>V) {
	return solve(N, M, A, B, U, V);
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e4 + 100;
const int mod = 1e9 + 7;

namespace {

	int A, B;
	string cur;
	vector<int>moves;
	bool flag = false;
	int go(vector<int>y) {
		int cnt = y[0] + y[1];
		if (flag) {
			if (cnt == 1) {
				moves.pb((y[0] > 0 ? 0 : 1));
			} else {
				moves.pb(moves.back() ^ 1);
			}
		} else {
			if (cnt == 1) {
				moves.pb((y[0] > 0 ? 0 : 1));
				goto done;
				if (!sz(moves)) {
					flag = true;
					moves.pb((y[0] > 0 ? 0 : 1));
				} else {
					if (sz(moves) < 4) {
						moves.pb((y[0] > 0 ? 0 : 1));
					} else {
						string t;
						for (int move : moves) {
							t += (move + '0');
						}
						t += (y[0] > 0 ? '0' : '1');
						string s = "010011";
						bool chk = false;
						for (int rot = 0; rot < 6; rot++) {
							if (s == t) {
								chk = true;
							}
							rotate(t.begin(), t.begin() + 1, t.end());
						}
						if (chk) {
							flag = true;
							moves.pb(y[0] > 0 ? 0 : 1);
						} else {
							flag = true;
							moves.pb(moves.back());
							return -1;
						}
					}
				}
			} else if (cnt == 2) {
				if (!sz(moves)) {
					if (y[0] && y[1]) {
						moves.pb(0), moves.pb(1);
					} else if (y[0]) {
						moves.pb(0), moves.pb(0);
					} else {
						moves.pb(1), moves.pb(1);
					}
				} else {
					if (!y[0] || !y[1]) {
						flag = true;
						moves.pb(moves.back());
						return -1;
					} else {
						flag = true;
						moves.pb(moves.back() ^ 1);
					}
				}
			} else if (cnt >= 3) {
				flag = true;
				if (!sz(moves)) {
					moves.pb((y[0] == 1 ? 0 : 1));
				} else {
					if (!y[0] || !y[1]) {
						moves.pb(moves.back());
						return -1;
					} else {
						moves.pb(moves.back() ^ 1);
					}
				}
			}
		}

		done: ;
		return moves.back();
	}
}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
}

int Move(vector<int>y) {
	if (A >= 3) {
		for (int i = 0; i < 3; i++) {
			if (y[i] > 0 && y[(i + 1) % 3] > 0) {
				return i;
			}
		}
		for (int i = 0; i < 3; i++) {
			if (y[i] > 0) {
				return i;
			}
		}
	} else {
		return go(y);
	}
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:123:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 16060 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 51 ms 15284 KB Output is correct
4 Correct 75 ms 17012 KB Output is correct
5 Correct 76 ms 16884 KB Output is correct
6 Correct 61 ms 15732 KB Output is correct
7 Correct 64 ms 15732 KB Output is correct
8 Correct 85 ms 16360 KB Output is correct
9 Correct 72 ms 16508 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 16060 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 51 ms 15284 KB Output is correct
4 Correct 75 ms 17012 KB Output is correct
5 Correct 76 ms 16884 KB Output is correct
6 Correct 61 ms 15732 KB Output is correct
7 Correct 64 ms 15732 KB Output is correct
8 Correct 85 ms 16360 KB Output is correct
9 Correct 72 ms 16508 KB Output is correct
10 Correct 52 ms 13888 KB Output is correct
11 Correct 61 ms 13680 KB Output is correct
12 Correct 75 ms 13816 KB Output is correct
13 Correct 69 ms 13808 KB Output is correct
14 Correct 60 ms 14200 KB Output is correct
15 Correct 69 ms 14484 KB Output is correct
16 Correct 72 ms 16516 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13556 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 48 ms 13144 KB Output is correct
4 Correct 82 ms 14864 KB Output is correct
5 Correct 72 ms 14848 KB Output is correct
6 Correct 64 ms 13576 KB Output is correct
7 Correct 64 ms 13556 KB Output is correct
8 Correct 66 ms 14308 KB Output is correct
9 Correct 67 ms 14156 KB Output is correct
10 Correct 64 ms 14052 KB Output is correct
11 Correct 67 ms 14044 KB Output is correct
12 Correct 63 ms 14036 KB Output is correct
13 Correct 64 ms 14048 KB Output is correct
14 Correct 73 ms 14196 KB Output is correct
15 Correct 69 ms 14308 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 13556 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 48 ms 13144 KB Output is correct
4 Correct 82 ms 14864 KB Output is correct
5 Correct 72 ms 14848 KB Output is correct
6 Correct 64 ms 13576 KB Output is correct
7 Correct 64 ms 13556 KB Output is correct
8 Correct 66 ms 14308 KB Output is correct
9 Correct 67 ms 14156 KB Output is correct
10 Correct 64 ms 14052 KB Output is correct
11 Correct 67 ms 14044 KB Output is correct
12 Correct 63 ms 14036 KB Output is correct
13 Correct 64 ms 14048 KB Output is correct
14 Correct 73 ms 14196 KB Output is correct
15 Correct 69 ms 14308 KB Output is correct
16 Correct 51 ms 11896 KB Output is correct
17 Correct 51 ms 12024 KB Output is correct
18 Correct 64 ms 12008 KB Output is correct
19 Correct 52 ms 12008 KB Output is correct
20 Correct 58 ms 12532 KB Output is correct
21 Correct 67 ms 12336 KB Output is correct
22 Correct 68 ms 14324 KB Output is correct
23 Correct 61 ms 12016 KB Output is correct
24 Correct 55 ms 11888 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1792 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 12 ms 1792 KB Output is correct
5 Correct 11 ms 1792 KB Output is correct
6 Incorrect 11 ms 1792 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11628 KB Output is correct
2 Correct 60 ms 12936 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 59 ms 11384 KB Output is correct
5 Correct 65 ms 14460 KB Output is correct
6 Correct 79 ms 14396 KB Output is correct
7 Correct 69 ms 13448 KB Output is correct
8 Correct 57 ms 13604 KB Output is correct
9 Correct 77 ms 14440 KB Output is correct
10 Correct 86 ms 14416 KB Output is correct
11 Correct 74 ms 14412 KB Output is correct
12 Incorrect 51 ms 13404 KB Wrong Answer [5]
13 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11780 KB Output is correct
2 Correct 58 ms 12956 KB Output is correct
3 Correct 10 ms 1632 KB Output is correct
4 Correct 49 ms 11632 KB Output is correct
5 Correct 69 ms 14316 KB Output is correct
6 Incorrect 54 ms 13436 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -