oj.uz

Submission #279731

# Submission time Handle Problem Language Result Execution time Memory
279731 2020-08-22T10:25:54 Z tjd229 Stray Cat (JOI20_stray) C++14
15 / 100
 76 ms 17248 KB 
#include "Anthony.h"
#include <vector>
#include <queue>

namespace {

	std::vector<int> edge[20000];
	int d[20000], m[20000];
	bool inq[20000];

	const int pat[6] = { 1,0,1,1,0,0 };

	void dfs(int x, int from) {

		if (x > 0 && edge[x].size() > 2) {//junction
			if (pat[m[from]] == 1) m[x] = 1;
			else m[x] = 0;
		}
		int nxtm = (m[x] + 1) % 6;
		for (auto nxt : edge[x]) {
			if (nxt == from) continue;
			d[nxt] = 1 + d[x];
			m[nxt] = nxtm;
			dfs(nxt, x);
		}
	}
	void bfs(int src) {
		std::queue<int> q; q.push(src);
		inq[src] = 1;
		while (q.size()) {
			int x = q.front(); q.pop();
			for (auto nxt : edge[x]) {
				if (inq[nxt]) continue;
				d[nxt] = d[x] + 1;
				q.push(nxt); inq[nxt] = 1;
			}
		}
	}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
	std::vector<int> U, std::vector<int> V) {
	for (int i = 0; i < M; ++i) {
		int u = U[i], v = V[i];
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	std::vector<int> X;
	if (B) {//tree
		dfs(0, 0);

		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (d[u] > d[v]) u ^= v ^= u ^= v;
			X.push_back(pat[m[u]]);
		}
	}

	else {
		bfs(0);
		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (d[u] > d[v]) u ^= v ^= u ^= v;
			X.push_back(d[u] % 3);
		}
	}
	return X;
}

#include "Catherine.h"
#include <vector>

namespace {
	int _B;
	int _A;
	std::vector<int> hist;
	const int pat[6 + 6] = { 0,0,1,1,0,1,0,0,1,1,0,1 };//dn dir
	int mv = 0;
	bool dir = 0;
}  // namespace

void Init(int A, int B) {
	_A = A, _B = B;
}
int soft_move(std::vector<int> &y) {
	if (dir) {
		if (y[0] + y[1] > 1) {
			int prev = hist.back();
			++y[prev];
			int nxt = y[0] == 1 ? 0 : 1;
			hist.push_back(nxt);
		}
		else {
			int nxt = y[0] ? 0 : 1;
			hist.push_back(nxt);
		}
		return hist.back();
	}
	else {
		if (mv == 0) {//init
			if (y[1]==1 &&y[0] == 0) {//leaf
				dir = 1;
				hist.push_back(1);
				return 1;
			}
			else if (y[0] == 1 && y[1] == 0) {//leaf
				dir = 1;
				hist.push_back(0);
				return 0;
			}
			else if (y[0] + y[1] > 2) {//junc
				dir = 1;
				int nxt = y[0] == 1 ? 0 : 1;
				hist.push_back(nxt);
				return nxt;
			}
			while (y[0]--) hist.push_back(0);//1-way
			while (y[1]--) hist.push_back(1);
			++mv;
			return hist.back();
		}
		else if (y[0] + y[1] == 0) {//leaf;
			dir = 1;
			hist.push_back(hist.back());
			return -1;
		}
		else if (y[0] + y[1] > 1) {//junc 
			int prev = hist.back();
			int nxt = 1 - prev;
			dir = 1;

			if (y[nxt] == 1) {
				hist.push_back(nxt);
				return nxt;
			}
			else {
				hist.push_back(prev);
				return -1;
			}
		}
		else {//way
			int nxt = y[0] ? 0 : 1;
			if (mv++ == 3) {
				dir = 1;
				for (int s = 0; s < 6; ++s) {
					bool flag = 1;
					for (int i = 0; i < 5 && flag; ++i) {
						if (hist[i] != pat[s + i]) flag = 0;
					}
					if (flag) {
						hist.push_back(hist.back());
						return -1;
					}
				}
				hist.push_back(nxt);
				return hist.back();
			}
			else {
				hist.push_back(nxt);
				return hist.back();
			}
		}
	}
}
int hard_move(std::vector<int> &y) {
	if (y[0] == 0 && y[1]) return 1;
	else if (y[1] == 0 && y[2]) return 2;
	else return 0;
}
int Move(std::vector<int> y) {
	if (_B) return soft_move(y);
	else return hard_move(y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16116 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 50 ms 15488 KB Output is correct
4 Correct 64 ms 17248 KB Output is correct
5 Correct 63 ms 17100 KB Output is correct
6 Correct 56 ms 16188 KB Output is correct
7 Correct 50 ms 16056 KB Output is correct
8 Correct 60 ms 16612 KB Output is correct
9 Correct 65 ms 16828 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16116 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 50 ms 15488 KB Output is correct
4 Correct 64 ms 17248 KB Output is correct
5 Correct 63 ms 17100 KB Output is correct
6 Correct 56 ms 16188 KB Output is correct
7 Correct 50 ms 16056 KB Output is correct
8 Correct 60 ms 16612 KB Output is correct
9 Correct 65 ms 16828 KB Output is correct
10 Correct 53 ms 14144 KB Output is correct
11 Correct 63 ms 14024 KB Output is correct
12 Correct 63 ms 14120 KB Output is correct
13 Correct 53 ms 14192 KB Output is correct
14 Correct 53 ms 14400 KB Output is correct
15 Correct 54 ms 15104 KB Output is correct
16 Correct 59 ms 16964 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13712 KB Output is correct
2 Correct 1 ms 1640 KB Output is correct
3 Correct 39 ms 13112 KB Output is correct
4 Correct 61 ms 15328 KB Output is correct
5 Correct 63 ms 14916 KB Output is correct
6 Correct 50 ms 13872 KB Output is correct
7 Correct 48 ms 13808 KB Output is correct
8 Correct 54 ms 14308 KB Output is correct
9 Correct 62 ms 14296 KB Output is correct
10 Correct 54 ms 14164 KB Output is correct
11 Correct 58 ms 14252 KB Output is correct
12 Correct 55 ms 14164 KB Output is correct
13 Correct 65 ms 14160 KB Output is correct
14 Correct 57 ms 14424 KB Output is correct
15 Correct 62 ms 14412 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13712 KB Output is correct
2 Correct 1 ms 1640 KB Output is correct
3 Correct 39 ms 13112 KB Output is correct
4 Correct 61 ms 15328 KB Output is correct
5 Correct 63 ms 14916 KB Output is correct
6 Correct 50 ms 13872 KB Output is correct
7 Correct 48 ms 13808 KB Output is correct
8 Correct 54 ms 14308 KB Output is correct
9 Correct 62 ms 14296 KB Output is correct
10 Correct 54 ms 14164 KB Output is correct
11 Correct 58 ms 14252 KB Output is correct
12 Correct 55 ms 14164 KB Output is correct
13 Correct 65 ms 14160 KB Output is correct
14 Correct 57 ms 14424 KB Output is correct
15 Correct 62 ms 14412 KB Output is correct
16 Correct 45 ms 12260 KB Output is correct
17 Correct 43 ms 12156 KB Output is correct
18 Correct 44 ms 12020 KB Output is correct
19 Correct 45 ms 12252 KB Output is correct
20 Correct 60 ms 12844 KB Output is correct
21 Correct 47 ms 12492 KB Output is correct
22 Correct 57 ms 14564 KB Output is correct
23 Correct 44 ms 12108 KB Output is correct
24 Correct 59 ms 12268 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11988 KB Output is correct
2 Correct 51 ms 13228 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 41 ms 11688 KB Output is correct
5 Correct 72 ms 14412 KB Output is correct
6 Correct 62 ms 14660 KB Output is correct
7 Incorrect 56 ms 13436 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 12084 KB Output is correct
2 Correct 50 ms 12884 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 41 ms 11696 KB Output is correct
5 Correct 70 ms 14660 KB Output is correct
6 Correct 76 ms 14588 KB Output is correct
7 Correct 47 ms 13640 KB Output is correct
8 Incorrect 46 ms 13444 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -