oj.uz

Submission #212407

# Submission time Handle Problem Language Result Execution time Memory
212407 2020-03-22T21:47:36 Z JustasZ Stray Cat (JOI20_stray) C++14
100 / 100
 100 ms 17004 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 == 0) {
				flag = true;
				moves.pb(moves.back());
				return -1;
			}
			if (cnt == 1) {
				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 = "110010";
						bool chk = false;
						for (int rot = 0; rot < 6; rot++) {
							if (s.substr(0, 5) == t) {
								chk = true;
							}
							rotate(s.begin(), s.begin() + 1, s.end());
						}
						flag = true;
						if (chk) {
							moves.pb((y[0] > 0 ? 0 : 1));
						} else {
							moves.pb(moves.back());
							return -1;
						}
					}
				}
			} else {
				if (!sz(moves)) {
					if (cnt == 2) {
						moves.pb((y[0] > 0 ? 0 : 1));
						moves.pb((y[1] > 0 ? 1 : 0));
					} else {
						flag = true;
						moves.pb((y[0] == 1 ? 0 : 1));
					}
				} else {
					flag = true;
					if (!y[0] || !y[1]) {
						flag = true;
						moves.pb(moves.back());
						return -1;
					} else {
						flag = true;
						moves.pb(moves.back() ^ 1);
					}
				}
			}
		}

		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:113: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 82 ms 15924 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 54 ms 15416 KB Output is correct
4 Correct 73 ms 16884 KB Output is correct
5 Correct 82 ms 17004 KB Output is correct
6 Correct 68 ms 15732 KB Output is correct
7 Correct 71 ms 15704 KB Output is correct
8 Correct 82 ms 16512 KB Output is correct
9 Correct 90 ms 16484 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15924 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 54 ms 15416 KB Output is correct
4 Correct 73 ms 16884 KB Output is correct
5 Correct 82 ms 17004 KB Output is correct
6 Correct 68 ms 15732 KB Output is correct
7 Correct 71 ms 15704 KB Output is correct
8 Correct 82 ms 16512 KB Output is correct
9 Correct 90 ms 16484 KB Output is correct
10 Correct 59 ms 13768 KB Output is correct
11 Correct 61 ms 13956 KB Output is correct
12 Correct 62 ms 13896 KB Output is correct
13 Correct 62 ms 13804 KB Output is correct
14 Correct 65 ms 14116 KB Output is correct
15 Correct 77 ms 14596 KB Output is correct
16 Correct 76 ms 16556 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13548 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 56 ms 13116 KB Output is correct
4 Correct 82 ms 14800 KB Output is correct
5 Correct 76 ms 14916 KB Output is correct
6 Correct 60 ms 13572 KB Output is correct
7 Correct 59 ms 13524 KB Output is correct
8 Correct 83 ms 14208 KB Output is correct
9 Correct 73 ms 14332 KB Output is correct
10 Correct 70 ms 14036 KB Output is correct
11 Correct 88 ms 14068 KB Output is correct
12 Correct 88 ms 14080 KB Output is correct
13 Correct 64 ms 14032 KB Output is correct
14 Correct 69 ms 14300 KB Output is correct
15 Correct 64 ms 14292 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13548 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 56 ms 13116 KB Output is correct
4 Correct 82 ms 14800 KB Output is correct
5 Correct 76 ms 14916 KB Output is correct
6 Correct 60 ms 13572 KB Output is correct
7 Correct 59 ms 13524 KB Output is correct
8 Correct 83 ms 14208 KB Output is correct
9 Correct 73 ms 14332 KB Output is correct
10 Correct 70 ms 14036 KB Output is correct
11 Correct 88 ms 14068 KB Output is correct
12 Correct 88 ms 14080 KB Output is correct
13 Correct 64 ms 14032 KB Output is correct
14 Correct 69 ms 14300 KB Output is correct
15 Correct 64 ms 14292 KB Output is correct
16 Correct 60 ms 12024 KB Output is correct
17 Correct 49 ms 11896 KB Output is correct
18 Correct 55 ms 12032 KB Output is correct
19 Correct 59 ms 12120 KB Output is correct
20 Correct 66 ms 12744 KB Output is correct
21 Correct 57 ms 12280 KB Output is correct
22 Correct 66 ms 14508 KB Output is correct
23 Correct 56 ms 12104 KB Output is correct
24 Correct 58 ms 12024 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1536 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 10 ms 1548 KB Output is correct
4 Correct 11 ms 1792 KB Output is correct
5 Correct 11 ms 1792 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct
7 Correct 10 ms 1792 KB Output is correct
8 Correct 12 ms 1792 KB Output is correct
9 Correct 12 ms 1792 KB Output is correct
10 Correct 10 ms 1792 KB Output is correct
11 Correct 11 ms 1792 KB Output is correct
12 Correct 10 ms 1792 KB Output is correct
13 Correct 10 ms 1792 KB Output is correct
14 Correct 11 ms 1792 KB Output is correct
15 Correct 12 ms 1792 KB Output is correct
16 Correct 11 ms 1792 KB Output is correct
17 Correct 10 ms 1792 KB Output is correct
18 Correct 12 ms 1792 KB Output is correct
19 Correct 11 ms 1792 KB Output is correct
20 Correct 11 ms 1600 KB Output is correct
21 Correct 11 ms 1548 KB Output is correct
22 Correct 10 ms 1792 KB Output is correct
23 Correct 12 ms 1792 KB Output is correct
24 Correct 10 ms 1856 KB Output is correct
25 Correct 12 ms 1536 KB Output is correct
26 Correct 10 ms 1792 KB Output is correct
27 Correct 10 ms 1792 KB Output is correct
28 Correct 10 ms 1632 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11760 KB Output is correct
2 Correct 83 ms 13028 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 57 ms 11512 KB Output is correct
5 Correct 71 ms 14448 KB Output is correct
6 Correct 100 ms 14480 KB Output is correct
7 Correct 62 ms 13556 KB Output is correct
8 Correct 64 ms 13560 KB Output is correct
9 Correct 93 ms 14436 KB Output is correct
10 Correct 80 ms 14332 KB Output is correct
11 Correct 94 ms 14504 KB Output is correct
12 Correct 79 ms 14452 KB Output is correct
13 Correct 69 ms 14492 KB Output is correct
14 Correct 84 ms 14476 KB Output is correct
15 Correct 69 ms 14340 KB Output is correct
16 Correct 75 ms 14480 KB Output is correct
17 Correct 62 ms 14232 KB Output is correct
18 Correct 70 ms 14196 KB Output is correct
19 Correct 65 ms 14124 KB Output is correct
20 Correct 68 ms 14060 KB Output is correct
21 Correct 67 ms 14204 KB Output is correct
22 Correct 65 ms 14100 KB Output is correct
23 Correct 57 ms 11772 KB Output is correct
24 Correct 61 ms 11644 KB Output is correct
25 Correct 60 ms 12416 KB Output is correct
26 Correct 59 ms 12292 KB Output is correct
27 Correct 66 ms 13172 KB Output is correct
28 Correct 70 ms 13156 KB Output is correct
29 Correct 67 ms 13220 KB Output is correct
30 Correct 64 ms 13164 KB Output is correct
31 Correct 58 ms 11756 KB Output is correct
32 Correct 55 ms 11772 KB Output is correct
33 Correct 57 ms 12020 KB Output is correct
34 Correct 54 ms 12156 KB Output is correct
35 Correct 68 ms 12908 KB Output is correct
36 Correct 67 ms 13116 KB Output is correct
37 Correct 82 ms 12920 KB Output is correct
38 Correct 71 ms 12896 KB Output is correct
39 Correct 64 ms 13004 KB Output is correct
40 Correct 64 ms 13140 KB Output is correct
41 Correct 69 ms 13644 KB Output is correct
42 Correct 67 ms 13696 KB Output is correct
43 Correct 65 ms 13684 KB Output is correct
44 Correct 69 ms 13684 KB Output is correct
45 Correct 73 ms 13556 KB Output is correct
46 Correct 74 ms 13692 KB Output is correct
47 Correct 67 ms 12876 KB Output is correct
48 Correct 59 ms 12788 KB Output is correct
49 Correct 66 ms 12772 KB Output is correct
50 Correct 70 ms 12900 KB Output is correct
51 Correct 63 ms 11892 KB Output is correct
52 Correct 57 ms 11772 KB Output is correct
53 Correct 56 ms 11872 KB Output is correct
54 Correct 62 ms 12048 KB Output is correct
55 Correct 55 ms 11956 KB Output is correct
56 Correct 68 ms 11764 KB Output is correct
57 Correct 61 ms 11836 KB Output is correct
58 Correct 69 ms 11900 KB Output is correct
59 Correct 55 ms 11892 KB Output is correct
60 Correct 62 ms 11892 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11700 KB Output is correct
2 Correct 54 ms 12884 KB Output is correct
3 Correct 9 ms 1536 KB Output is correct
4 Correct 45 ms 11396 KB Output is correct
5 Correct 75 ms 14436 KB Output is correct
6 Correct 77 ms 14368 KB Output is correct
7 Correct 54 ms 13572 KB Output is correct
8 Correct 61 ms 13540 KB Output is correct
9 Correct 74 ms 14444 KB Output is correct
10 Correct 73 ms 14452 KB Output is correct
11 Correct 71 ms 14452 KB Output is correct
12 Correct 74 ms 14444 KB Output is correct
13 Correct 67 ms 14424 KB Output is correct
14 Correct 77 ms 14540 KB Output is correct
15 Correct 72 ms 14584 KB Output is correct
16 Correct 66 ms 14428 KB Output is correct
17 Correct 68 ms 14096 KB Output is correct
18 Correct 68 ms 14088 KB Output is correct
19 Correct 69 ms 14092 KB Output is correct
20 Correct 66 ms 14152 KB Output is correct
21 Correct 65 ms 14200 KB Output is correct
22 Correct 69 ms 14068 KB Output is correct
23 Correct 55 ms 11764 KB Output is correct
24 Correct 62 ms 11720 KB Output is correct
25 Correct 72 ms 12156 KB Output is correct
26 Correct 63 ms 12156 KB Output is correct
27 Correct 73 ms 13172 KB Output is correct
28 Correct 62 ms 13152 KB Output is correct
29 Correct 59 ms 13156 KB Output is correct
30 Correct 72 ms 13044 KB Output is correct
31 Correct 64 ms 11684 KB Output is correct
32 Correct 49 ms 11772 KB Output is correct
33 Correct 57 ms 12156 KB Output is correct
34 Correct 57 ms 12248 KB Output is correct
35 Correct 68 ms 13028 KB Output is correct
36 Correct 66 ms 12908 KB Output is correct
37 Correct 59 ms 12936 KB Output is correct
38 Correct 72 ms 12916 KB Output is correct
39 Correct 66 ms 13044 KB Output is correct
40 Correct 71 ms 12916 KB Output is correct
41 Correct 67 ms 13548 KB Output is correct
42 Correct 64 ms 13564 KB Output is correct
43 Correct 62 ms 13780 KB Output is correct
44 Correct 71 ms 13640 KB Output is correct
45 Correct 76 ms 13704 KB Output is correct
46 Correct 70 ms 13684 KB Output is correct
47 Correct 61 ms 12796 KB Output is correct
48 Correct 66 ms 12900 KB Output is correct
49 Correct 68 ms 12788 KB Output is correct
50 Correct 75 ms 12900 KB Output is correct
51 Correct 55 ms 11904 KB Output is correct
52 Correct 50 ms 12028 KB Output is correct
53 Correct 55 ms 11988 KB Output is correct
54 Correct 59 ms 11984 KB Output is correct
55 Correct 59 ms 11772 KB Output is correct
56 Correct 65 ms 11892 KB Output is correct
57 Correct 60 ms 11896 KB Output is correct
58 Correct 53 ms 11908 KB Output is correct
59 Correct 52 ms 11772 KB Output is correct
60 Correct 54 ms 11860 KB Output is correct