답안 #279740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
279740	2020-08-22T10:33:20 Z	tjd229	길고양이 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #279740

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 2.0 / 2.0

Subtask #3 2.0 / 2.0

Subtask #4 9.0 / 9.0

Subtask #5 5.0 / 5.0

Subtask #6 71.0 / 71.0

Subtask #7 9.0 / 9.0

Subtask #1
2.0 / 2.0

Subtask #2
2.0 / 2.0

Subtask #3
2.0 / 2.0

Subtask #4
9.0 / 9.0

Subtask #5
5.0 / 5.0

Subtask #6
71.0 / 71.0

Subtask #7
9.0 / 9.0