oj.uz

Submission #670639

# Submission time Handle Problem Language Result Execution time Memory
670639 2022-12-09T19:25:09 Z rainboy Stray Cat (JOI20_stray) C++17
20 / 100
 48 ms 16360 KB 
#include "Anthony.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace A {
	const int N = 20000;
	const int zz[] = { 0, 1, 0, 0, 1, 1 };

	int min(int a, int b) { return a < b ? a : b; }

	int *ej[N], eo[N], dd[N], pp[N], cc_[N], qu[N], n;

	void init(int n_) {
		n = n_;
		for (int i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	}

	void append(int i, int j) {
		int o = eo[i]++;
		if (o >= 2 && (o & o - 1) == 0)
			ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ej[i][o] = j;
	}

	void bfs() {
		for (int i = 0; i < n; i++)
			dd[i] = n;
		int cnt = 0;
		dd[0] = 0, qu[cnt++] = 0;
		for (int h = 0; h < cnt; h++) {
			int i = qu[h], d = dd[i] + 1;
			for (int o = eo[i]; o--; ) {
				int j = ej[i][o];
				if (dd[j] > d)
					dd[j] = d, qu[cnt++] = j;
			}
		}
	}
	void dfs(int p, int i, int c) {
		pp[i] = p;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p) {
				if (p == -1)
					cc_[j] = 0, dfs(i, j, 0);
				else if (eo[i] == 2)
					cc_[j] = zz[(c + 1) % 6], dfs(i, j, (c + 1) % 6);
				else
					cc_[j] = zz[c % 6] ^ 1, dfs(i, j, zz[c % 6] ^ 1);
			}
		}
	}
}

vi Mark(int n, int m, int a, int b, vi uu, vi vv) {
	vi cc(m);
	if (a >= 3 && b == 0) {
		A::init(n);
		for (int h = 0; h < m; h++)
			A::append(uu[h], vv[h]), A::append(vv[h], uu[h]);
		A::bfs();
		for (int h = 0; h < m; h++)
			cc[h] = A::min(A::dd[uu[h]], A::dd[vv[h]]) % 3;
	} else {
		A::init(n);
		for (int h = 0; h < m; h++)
			A::append(uu[h], vv[h]), A::append(vv[h], uu[h]);
		A::dfs(-1, 0, -1);
		for (int h = 0; h < m; h++) {
			int i = A::pp[uu[h]] == vv[h] ? uu[h] : vv[h];
			cc[h] = A::cc_[i];
		}
	}
	return cc;
}
#include "Catherine.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace B {
	const int zz[] = { 0, 1, 0, 0, 1, 1 };
	int cc[6], h, c_;
}

void Init(int a, int b) {
	a = b = a;
	B::h = 0, B::c_ = -1;
}

int Move(vi kk) {
	int a = kk.size();
	if (a >= 3) {
		for (int c = 0; c < 3; c++)
			if (kk[(c + 2) % 3] == 0 && kk[c] != 0)
				return c;
		return -1;
	} else {
		int d = B::c_ != -1 ? 1 : 0;
		for (int c = 0; c < 2; c++)
			d += kk[c];
		if (d == 1) {
			B::h = -1;
			for (int c = 0; c < 2; c++)
				if (kk[c] != 0)
					return B::c_ = c;
			return -1;
		} else if (d == 2) {
			if (B::h == -1) {
				for (int c = 0; c < 2; c++)
					if (kk[c] != 0)
						return B::c_ = c;
				return -1;
			} else {
				for (int c = 0; c < 2; c++)
					if (kk[c] != 0)
						B::cc[B::h++] = c;
				if (B::h < 5)
					return B::c_ = B::cc[B::h - 1];
				else {
					for (int g = 0; g < 6; g++) {
						int match = 1;
						for (int h = 0; h < 5; h++)
							if (B::zz[(g + h) % 6]) {
								match = 0;
								break;
							}
						if (match) {
							B::h = -1;
							return -1;
						}
					}
					B::h = -1;
					return B::c_ = B::cc[4];
				}
			}
		} else {
			B::h = -1;
			return B::c_ == -1 ? (kk[0] == 1 ? 0 : 1) : kk[B::c_] == 0 ? -1 : (B::c_ ^= 1);
		}
	}
}

Compilation message

Anthony.cpp: In function 'void A::append(int, int)':
Anthony.cpp:25:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   25 |   if (o >= 2 && (o & o - 1) == 0)
      |                      ~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15020 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 28 ms 14528 KB Output is correct
4 Correct 42 ms 16252 KB Output is correct
5 Correct 44 ms 16360 KB Output is correct
6 Correct 37 ms 14912 KB Output is correct
7 Correct 33 ms 14944 KB Output is correct
8 Correct 38 ms 15632 KB Output is correct
9 Correct 39 ms 15708 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15020 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 28 ms 14528 KB Output is correct
4 Correct 42 ms 16252 KB Output is correct
5 Correct 44 ms 16360 KB Output is correct
6 Correct 37 ms 14912 KB Output is correct
7 Correct 33 ms 14944 KB Output is correct
8 Correct 38 ms 15632 KB Output is correct
9 Correct 39 ms 15708 KB Output is correct
10 Correct 30 ms 12988 KB Output is correct
11 Correct 28 ms 13048 KB Output is correct
12 Correct 30 ms 13004 KB Output is correct
13 Correct 31 ms 13008 KB Output is correct
14 Correct 31 ms 13252 KB Output is correct
15 Correct 35 ms 13668 KB Output is correct
16 Correct 41 ms 15828 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12756 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 12644 KB Output is correct
4 Correct 48 ms 14044 KB Output is correct
5 Correct 42 ms 13996 KB Output is correct
6 Correct 32 ms 12760 KB Output is correct
7 Correct 33 ms 12732 KB Output is correct
8 Correct 36 ms 13408 KB Output is correct
9 Correct 37 ms 13424 KB Output is correct
10 Correct 35 ms 13116 KB Output is correct
11 Correct 39 ms 13092 KB Output is correct
12 Correct 36 ms 13100 KB Output is correct
13 Correct 35 ms 13080 KB Output is correct
14 Correct 36 ms 13384 KB Output is correct
15 Correct 36 ms 13456 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12756 KB Output is correct
2 Correct 0 ms 508 KB Output is correct
3 Correct 28 ms 12644 KB Output is correct
4 Correct 48 ms 14044 KB Output is correct
5 Correct 42 ms 13996 KB Output is correct
6 Correct 32 ms 12760 KB Output is correct
7 Correct 33 ms 12732 KB Output is correct
8 Correct 36 ms 13408 KB Output is correct
9 Correct 37 ms 13424 KB Output is correct
10 Correct 35 ms 13116 KB Output is correct
11 Correct 39 ms 13092 KB Output is correct
12 Correct 36 ms 13100 KB Output is correct
13 Correct 35 ms 13080 KB Output is correct
14 Correct 36 ms 13384 KB Output is correct
15 Correct 36 ms 13456 KB Output is correct
16 Correct 27 ms 11208 KB Output is correct
17 Correct 27 ms 11204 KB Output is correct
18 Correct 30 ms 11212 KB Output is correct
19 Correct 28 ms 11232 KB Output is correct
20 Correct 35 ms 11704 KB Output is correct
21 Correct 31 ms 11484 KB Output is correct
22 Correct 36 ms 13664 KB Output is correct
23 Correct 31 ms 11272 KB Output is correct
24 Correct 30 ms 11308 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 0 ms 516 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 904 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 1 ms 904 KB Output is correct
13 Correct 2 ms 892 KB Output is correct
14 Correct 1 ms 904 KB Output is correct
15 Correct 2 ms 900 KB Output is correct
16 Correct 2 ms 904 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 1 ms 900 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 1 ms 908 KB Output is correct
22 Correct 2 ms 908 KB Output is correct
23 Correct 1 ms 896 KB Output is correct
24 Correct 2 ms 844 KB Output is correct
25 Correct 1 ms 896 KB Output is correct
26 Correct 1 ms 900 KB Output is correct
27 Correct 2 ms 896 KB Output is correct
28 Correct 1 ms 908 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11008 KB Output is correct
2 Correct 33 ms 12360 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 25 ms 10848 KB Output is correct
5 Correct 43 ms 13980 KB Output is correct
6 Correct 37 ms 13968 KB Output is correct
7 Incorrect 27 ms 13028 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10968 KB Output is correct
2 Correct 32 ms 12160 KB Output is correct
3 Correct 0 ms 516 KB Output is correct
4 Correct 26 ms 11096 KB Output is correct
5 Correct 37 ms 14032 KB Output is correct
6 Correct 37 ms 14340 KB Output is correct
7 Correct 32 ms 13560 KB Output is correct
8 Correct 31 ms 13512 KB Output is correct
9 Correct 38 ms 14492 KB Output is correct
10 Correct 39 ms 14392 KB Output is correct
11 Correct 36 ms 14324 KB Output is correct
12 Correct 37 ms 14424 KB Output is correct
13 Correct 37 ms 13964 KB Output is correct
14 Correct 36 ms 14120 KB Output is correct
15 Incorrect 34 ms 14020 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -