oj.uz

Submission #279740

# Submission time Handle Problem Language Result Execution time Memory
279740 2020-08-22T10:33:20 Z tjd229 Stray Cat (JOI20_stray) C++14
100 / 100
 77 ms 17244 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] = { 1,0,1,1,0,0 ,1,0,1,1,0,0 };//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) {
				hist.push_back(nxt);
				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.pop_back();
						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 58 ms 16084 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 48 ms 15412 KB Output is correct
4 Correct 73 ms 17100 KB Output is correct
5 Correct 77 ms 17244 KB Output is correct
6 Correct 54 ms 16016 KB Output is correct
7 Correct 50 ms 15952 KB Output is correct
8 Correct 59 ms 16468 KB Output is correct
9 Correct 60 ms 16596 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16084 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 48 ms 15412 KB Output is correct
4 Correct 73 ms 17100 KB Output is correct
5 Correct 77 ms 17244 KB Output is correct
6 Correct 54 ms 16016 KB Output is correct
7 Correct 50 ms 15952 KB Output is correct
8 Correct 59 ms 16468 KB Output is correct
9 Correct 60 ms 16596 KB Output is correct
10 Correct 46 ms 13888 KB Output is correct
11 Correct 47 ms 14120 KB Output is correct
12 Correct 46 ms 14108 KB Output is correct
13 Correct 45 ms 14060 KB Output is correct
14 Correct 46 ms 14392 KB Output is correct
15 Correct 55 ms 14772 KB Output is correct
16 Correct 56 ms 16932 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13656 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 40 ms 13328 KB Output is correct
4 Correct 60 ms 14932 KB Output is correct
5 Correct 62 ms 15076 KB Output is correct
6 Correct 47 ms 13780 KB Output is correct
7 Correct 46 ms 13892 KB Output is correct
8 Correct 53 ms 14444 KB Output is correct
9 Correct 57 ms 14312 KB Output is correct
10 Correct 53 ms 14164 KB Output is correct
11 Correct 52 ms 14180 KB Output is correct
12 Correct 51 ms 14176 KB Output is correct
13 Correct 52 ms 14348 KB Output is correct
14 Correct 59 ms 14508 KB Output is correct
15 Correct 56 ms 14420 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13656 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 40 ms 13328 KB Output is correct
4 Correct 60 ms 14932 KB Output is correct
5 Correct 62 ms 15076 KB Output is correct
6 Correct 47 ms 13780 KB Output is correct
7 Correct 46 ms 13892 KB Output is correct
8 Correct 53 ms 14444 KB Output is correct
9 Correct 57 ms 14312 KB Output is correct
10 Correct 53 ms 14164 KB Output is correct
11 Correct 52 ms 14180 KB Output is correct
12 Correct 51 ms 14176 KB Output is correct
13 Correct 52 ms 14348 KB Output is correct
14 Correct 59 ms 14508 KB Output is correct
15 Correct 56 ms 14420 KB Output is correct
16 Correct 40 ms 12160 KB Output is correct
17 Correct 40 ms 12108 KB Output is correct
18 Correct 43 ms 12196 KB Output is correct
19 Correct 43 ms 12108 KB Output is correct
20 Correct 61 ms 12652 KB Output is correct
21 Correct 54 ms 12696 KB Output is correct
22 Correct 57 ms 14420 KB Output is correct
23 Correct 44 ms 12328 KB Output is correct
24 Correct 46 ms 12228 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 2 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 Correct 2 ms 1792 KB Output is correct
10 Correct 4 ms 1792 KB Output is correct
11 Correct 2 ms 1792 KB Output is correct
12 Correct 2 ms 1792 KB Output is correct
13 Correct 2 ms 1792 KB Output is correct
14 Correct 2 ms 1792 KB Output is correct
15 Correct 2 ms 1792 KB Output is correct
16 Correct 2 ms 1536 KB Output is correct
17 Correct 3 ms 1536 KB Output is correct
18 Correct 3 ms 1536 KB Output is correct
19 Correct 2 ms 1536 KB Output is correct
20 Correct 2 ms 1536 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 1536 KB Output is correct
23 Correct 2 ms 1536 KB Output is correct
24 Correct 2 ms 1536 KB Output is correct
25 Correct 2 ms 1536 KB Output is correct
26 Correct 2 ms 1536 KB Output is correct
27 Correct 2 ms 1536 KB Output is correct
28 Correct 2 ms 1536 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 11976 KB Output is correct
2 Correct 49 ms 13400 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 40 ms 11560 KB Output is correct
5 Correct 60 ms 14540 KB Output is correct
6 Correct 60 ms 14740 KB Output is correct
7 Correct 48 ms 13524 KB Output is correct
8 Correct 46 ms 13636 KB Output is correct
9 Correct 57 ms 14420 KB Output is correct
10 Correct 64 ms 14420 KB Output is correct
11 Correct 61 ms 14412 KB Output is correct
12 Correct 63 ms 14660 KB Output is correct
13 Correct 61 ms 14720 KB Output is correct
14 Correct 59 ms 14644 KB Output is correct
15 Correct 71 ms 14612 KB Output is correct
16 Correct 60 ms 14412 KB Output is correct
17 Correct 54 ms 14276 KB Output is correct
18 Correct 60 ms 14164 KB Output is correct
19 Correct 56 ms 14164 KB Output is correct
20 Correct 55 ms 14372 KB Output is correct
21 Correct 68 ms 14288 KB Output is correct
22 Correct 56 ms 14280 KB Output is correct
23 Correct 44 ms 12024 KB Output is correct
24 Correct 43 ms 11860 KB Output is correct
25 Correct 45 ms 12428 KB Output is correct
26 Correct 46 ms 12524 KB Output is correct
27 Correct 52 ms 13132 KB Output is correct
28 Correct 57 ms 13184 KB Output is correct
29 Correct 56 ms 13260 KB Output is correct
30 Correct 53 ms 13352 KB Output is correct
31 Correct 51 ms 11980 KB Output is correct
32 Correct 45 ms 11988 KB Output is correct
33 Correct 44 ms 12372 KB Output is correct
34 Correct 45 ms 12368 KB Output is correct
35 Correct 62 ms 12876 KB Output is correct
36 Correct 52 ms 12884 KB Output is correct
37 Correct 52 ms 13028 KB Output is correct
38 Correct 52 ms 13304 KB Output is correct
39 Correct 54 ms 13032 KB Output is correct
40 Correct 52 ms 13044 KB Output is correct
41 Correct 53 ms 13880 KB Output is correct
42 Correct 54 ms 13648 KB Output is correct
43 Correct 53 ms 13728 KB Output is correct
44 Correct 53 ms 13772 KB Output is correct
45 Correct 55 ms 13760 KB Output is correct
46 Correct 54 ms 13764 KB Output is correct
47 Correct 48 ms 13112 KB Output is correct
48 Correct 53 ms 12960 KB Output is correct
49 Correct 49 ms 12968 KB Output is correct
50 Correct 50 ms 13012 KB Output is correct
51 Correct 44 ms 12332 KB Output is correct
52 Correct 44 ms 12276 KB Output is correct
53 Correct 44 ms 12316 KB Output is correct
54 Correct 44 ms 12244 KB Output is correct
55 Correct 43 ms 12116 KB Output is correct
56 Correct 44 ms 12244 KB Output is correct
57 Correct 45 ms 12332 KB Output is correct
58 Correct 45 ms 12336 KB Output is correct
59 Correct 52 ms 12324 KB Output is correct
60 Correct 45 ms 12116 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11996 KB Output is correct
2 Correct 56 ms 13012 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 44 ms 11824 KB Output is correct
5 Correct 56 ms 14656 KB Output is correct
6 Correct 63 ms 14540 KB Output is correct
7 Correct 47 ms 13428 KB Output is correct
8 Correct 59 ms 13644 KB Output is correct
9 Correct 67 ms 14540 KB Output is correct
10 Correct 66 ms 14820 KB Output is correct
11 Correct 69 ms 14404 KB Output is correct
12 Correct 62 ms 14664 KB Output is correct
13 Correct 58 ms 14640 KB Output is correct
14 Correct 73 ms 14532 KB Output is correct
15 Correct 71 ms 14660 KB Output is correct
16 Correct 65 ms 14660 KB Output is correct
17 Correct 54 ms 14292 KB Output is correct
18 Correct 54 ms 14164 KB Output is correct
19 Correct 53 ms 14268 KB Output is correct
20 Correct 54 ms 14208 KB Output is correct
21 Correct 54 ms 14164 KB Output is correct
22 Correct 59 ms 14164 KB Output is correct
23 Correct 54 ms 11972 KB Output is correct
24 Correct 44 ms 12024 KB Output is correct
25 Correct 49 ms 12360 KB Output is correct
26 Correct 55 ms 12544 KB Output is correct
27 Correct 55 ms 13124 KB Output is correct
28 Correct 55 ms 13132 KB Output is correct
29 Correct 60 ms 13352 KB Output is correct
30 Correct 51 ms 13260 KB Output is correct
31 Correct 43 ms 12196 KB Output is correct
32 Correct 43 ms 11988 KB Output is correct
33 Correct 45 ms 12416 KB Output is correct
34 Correct 45 ms 12384 KB Output is correct
35 Correct 61 ms 13004 KB Output is correct
36 Correct 50 ms 13004 KB Output is correct
37 Correct 51 ms 13012 KB Output is correct
38 Correct 53 ms 13028 KB Output is correct
39 Correct 55 ms 13040 KB Output is correct
40 Correct 52 ms 13076 KB Output is correct
41 Correct 55 ms 13880 KB Output is correct
42 Correct 55 ms 13876 KB Output is correct
43 Correct 53 ms 13780 KB Output is correct
44 Correct 59 ms 13644 KB Output is correct
45 Correct 58 ms 13884 KB Output is correct
46 Correct 60 ms 13876 KB Output is correct
47 Correct 53 ms 12952 KB Output is correct
48 Correct 48 ms 12876 KB Output is correct
49 Correct 47 ms 12956 KB Output is correct
50 Correct 48 ms 12876 KB Output is correct
51 Correct 43 ms 12236 KB Output is correct
52 Correct 56 ms 12396 KB Output is correct
53 Correct 46 ms 12244 KB Output is correct
54 Correct 48 ms 12108 KB Output is correct
55 Correct 47 ms 12316 KB Output is correct
56 Correct 49 ms 12308 KB Output is correct
57 Correct 44 ms 12324 KB Output is correct
58 Correct 45 ms 12244 KB Output is correct
59 Correct 45 ms 12316 KB Output is correct
60 Correct 46 ms 12328 KB Output is correct