oj.uz

Submission #279704

# Submission time Handle Problem Language Result Execution time Memory
279704 2020-08-22T10:00:07 Z tjd229 Stray Cat (JOI20_stray) C++14
15 / 100
 77 ms 17216 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[0] == 0) {//leaf
				dir = 1;
				hist.push_back(1);
				return 1;
			}
			else if (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 57 ms 16088 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 49 ms 15492 KB Output is correct
4 Correct 64 ms 17192 KB Output is correct
5 Correct 69 ms 17216 KB Output is correct
6 Correct 48 ms 15944 KB Output is correct
7 Correct 53 ms 15944 KB Output is correct
8 Correct 65 ms 16584 KB Output is correct
9 Correct 70 ms 16684 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16088 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 49 ms 15492 KB Output is correct
4 Correct 64 ms 17192 KB Output is correct
5 Correct 69 ms 17216 KB Output is correct
6 Correct 48 ms 15944 KB Output is correct
7 Correct 53 ms 15944 KB Output is correct
8 Correct 65 ms 16584 KB Output is correct
9 Correct 70 ms 16684 KB Output is correct
10 Correct 43 ms 13908 KB Output is correct
11 Correct 44 ms 13880 KB Output is correct
12 Correct 57 ms 14164 KB Output is correct
13 Correct 45 ms 14080 KB Output is correct
14 Correct 47 ms 14276 KB Output is correct
15 Correct 55 ms 14532 KB Output is correct
16 Correct 58 ms 16620 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13748 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 13196 KB Output is correct
4 Correct 72 ms 15044 KB Output is correct
5 Correct 77 ms 15368 KB Output is correct
6 Correct 54 ms 13636 KB Output is correct
7 Correct 53 ms 13880 KB Output is correct
8 Correct 56 ms 14304 KB Output is correct
9 Correct 55 ms 14308 KB Output is correct
10 Correct 52 ms 14172 KB Output is correct
11 Correct 53 ms 14164 KB Output is correct
12 Correct 50 ms 14172 KB Output is correct
13 Correct 51 ms 14164 KB Output is correct
14 Correct 55 ms 14424 KB Output is correct
15 Correct 56 ms 14800 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13748 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 13196 KB Output is correct
4 Correct 72 ms 15044 KB Output is correct
5 Correct 77 ms 15368 KB Output is correct
6 Correct 54 ms 13636 KB Output is correct
7 Correct 53 ms 13880 KB Output is correct
8 Correct 56 ms 14304 KB Output is correct
9 Correct 55 ms 14308 KB Output is correct
10 Correct 52 ms 14172 KB Output is correct
11 Correct 53 ms 14164 KB Output is correct
12 Correct 50 ms 14172 KB Output is correct
13 Correct 51 ms 14164 KB Output is correct
14 Correct 55 ms 14424 KB Output is correct
15 Correct 56 ms 14800 KB Output is correct
16 Correct 43 ms 12156 KB Output is correct
17 Correct 41 ms 12144 KB Output is correct
18 Correct 41 ms 12108 KB Output is correct
19 Correct 43 ms 12108 KB Output is correct
20 Correct 50 ms 12868 KB Output is correct
21 Correct 47 ms 12724 KB Output is correct
22 Correct 53 ms 14480 KB Output is correct
23 Correct 43 ms 12364 KB Output is correct
24 Correct 44 ms 12320 KB Output is correct

Subtask #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 Incorrect 2 ms 1792 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11880 KB Output is correct
2 Incorrect 43 ms 12780 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11948 KB Output is correct
2 Correct 46 ms 13220 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 41 ms 11696 KB Output is correct
5 Correct 56 ms 14412 KB Output is correct
6 Correct 57 ms 14332 KB Output is correct
7 Correct 50 ms 13640 KB Output is correct
8 Incorrect 47 ms 13644 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -