oj.uz

Submission #246349

# Submission time Handle Problem Language Result Execution time Memory
246349 2020-07-08T19:12:45 Z kostia244 Stray Cat (JOI20_stray) C++17
89 / 100
 80 ms 22916 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;


namespace anton {
const int maxn = 1<<17;
vector<int> val, p, pidx, col,  god = {0, 0, 1, 0, 1, 1};
vector<array<int, 2>> g[maxn];
void dfs(int v) {
	for(auto &[i, idx] : g[v]) if(i != p[v]) {
		p[i] = v, pidx[i] = idx;
		col[i] = col[v]^1;
		dfs(i);
	}
	//cout << v << " // " << col[v] << '\n';
	if(!v || g[v].size() == 2) return;
	int u = p[v];
	vector<int> l {v};
	while(u && g[u].size() == 2) {
		l.pb(u);
		u = p[u];
	}
	int b = 0;
	while(god[b] != col[v] || god[(b + l.size() - 1)%6] != col[l.back()]) b++;
	//cout << v << " /// " << b << endl;
	//cout << god[b] << " vs " << col[v] << '\n';
	for(int i = 0; i < l.size(); i++) val[pidx[l[i]]] = god[(i+b)%6];
}

} 

namespace antOn {
const int maxn = 1<<17;
	vector<array<int, 2>> g[maxn];
	vector<int> val, lvl;
	queue<int> q;
	void solve() {
		lvl[0] = 0;
		q.push(0);
		vector<array<int, 3>> edges(val.size());
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(auto &[i, idx] : g[u]) {
				if(lvl[i] == -1) {
					lvl[i] = lvl[u] + 1;
					q.push(i);
				}
				edges[idx] = {i, u, idx};
			}
		}
		for(auto [u, v, idx] : edges) val[idx] = (min(lvl[v], lvl[u]) + (lvl[u]==lvl[v]))%3;
	}
}

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
	if(B == 0) {
	  for(int i = 0; i < M; i++) {
		antOn::g[U[i]].pb({V[i], i});
		antOn::g[V[i]].pb({U[i], i});
	}
	antOn::val.resize(M);
	antOn::lvl.resize(N, -1);
	antOn::solve();
	return antOn::val;
  }
  using namespace anton;
  val.resize(M);
  for(int i = 0; i < M; i++) {
	  g[U[i]].pb({V[i], i});
	  g[V[i]].pb({U[i], i});
  }
  p.resize(N);
  pidx.resize(N);
  col.resize(N);
  dfs(0);
  //for(int i = 0; i < M; i++) cout << U[i] << " " << V[i] << " " << val[i] << '\n';
  return val;
}

#include "Catherine.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

namespace kate {

int A, B, gg = 0, lst = -2, mvs = 0;
string cur, god = "110100110100";
int decide(vector<int> c) {
	if(B == 0) {
		if(!c[0] && !c[1]) return 2;
		if(!c[0] && !c[2]) return 1;
		if(!c[1] && !c[2]) return 0;
		if(c[0] && c[1]) return 0;
		if(c[2] && c[1]) return 1;
		if(c[2] && c[0]) return 2;
	}
	if(mvs++ > 10 && !gg) exit(-1);
	if(c[0] + c[1] == 0) {
		gg = 1;
		return -1;
	}
	if(lst == -2 && c[0]+c[1] == 1) {
		gg = 1;
		return lst = c[1];
	}
	if(c[0] + c[1] + (lst != -2) > 2) {
		gg = 1;
		if(c[0] == 0) return -1;
		if(c[1] == 0) return -1;
		if(c[0] == 1 && lst != 0) return lst = 0;
		if(c[1] == 1 && lst != 1) return lst = 1;
		exit(-1);
	}
	if(c[0] + c[1] == 2) {
		if(c[0]) {
			cur.pb('0'+c[1]);
			cur.pb('0');
			return lst = 0;
		}
		cur += "11";
		return lst = 1;
	}
	if(gg) return lst = c[1];
	cur.pb('0'+c[1]);
	if(cur.size() == 5) {
		gg = 1;
		//cout << " " << gg << "Yay\n";
		if(god.find(cur) != string::npos) return -1;
	}
	return lst = c[1];
}


}  // namespace

void Init(int A, int B) {
	kate::A = A;
	kate::B = B;
}

int Move(std::vector<int> y) {
	//cout << y[0] << " " << y[1] << " go ";
	int t = kate::decide(y);
	//cout <<kate::cur << " " << t << endl;
	return t;
}

Compilation message

Anthony.cpp: In function 'void anton::dfs(int)':
Anthony.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < l.size(); i++) val[pidx[l[i]]] = god[(i+b)%6];
                 ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 21924 KB Output is correct
2 Correct 12 ms 13056 KB Output is correct
3 Correct 50 ms 21272 KB Output is correct
4 Correct 73 ms 22892 KB Output is correct
5 Correct 70 ms 22916 KB Output is correct
6 Correct 59 ms 21612 KB Output is correct
7 Correct 57 ms 21788 KB Output is correct
8 Correct 67 ms 22468 KB Output is correct
9 Correct 66 ms 22216 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 21924 KB Output is correct
2 Correct 12 ms 13056 KB Output is correct
3 Correct 50 ms 21272 KB Output is correct
4 Correct 73 ms 22892 KB Output is correct
5 Correct 70 ms 22916 KB Output is correct
6 Correct 59 ms 21612 KB Output is correct
7 Correct 57 ms 21788 KB Output is correct
8 Correct 67 ms 22468 KB Output is correct
9 Correct 66 ms 22216 KB Output is correct
10 Correct 56 ms 20028 KB Output is correct
11 Incorrect 53 ms 19888 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 19468 KB Output is correct
2 Correct 12 ms 13056 KB Output is correct
3 Correct 48 ms 19120 KB Output is correct
4 Correct 69 ms 20588 KB Output is correct
5 Correct 69 ms 20584 KB Output is correct
6 Correct 55 ms 19472 KB Output is correct
7 Correct 54 ms 19432 KB Output is correct
8 Correct 64 ms 20296 KB Output is correct
9 Correct 64 ms 20280 KB Output is correct
10 Correct 61 ms 20008 KB Output is correct
11 Correct 58 ms 20040 KB Output is correct
12 Correct 61 ms 20060 KB Output is correct
13 Correct 59 ms 19952 KB Output is correct
14 Correct 64 ms 20136 KB Output is correct
15 Correct 63 ms 20420 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 19468 KB Output is correct
2 Correct 12 ms 13056 KB Output is correct
3 Correct 48 ms 19120 KB Output is correct
4 Correct 69 ms 20588 KB Output is correct
5 Correct 69 ms 20584 KB Output is correct
6 Correct 55 ms 19472 KB Output is correct
7 Correct 54 ms 19432 KB Output is correct
8 Correct 64 ms 20296 KB Output is correct
9 Correct 64 ms 20280 KB Output is correct
10 Correct 61 ms 20008 KB Output is correct
11 Correct 58 ms 20040 KB Output is correct
12 Correct 61 ms 20060 KB Output is correct
13 Correct 59 ms 19952 KB Output is correct
14 Correct 64 ms 20136 KB Output is correct
15 Correct 63 ms 20420 KB Output is correct
16 Incorrect 59 ms 17900 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

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

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 17960 KB Output is correct
2 Correct 60 ms 18996 KB Output is correct
3 Correct 12 ms 13056 KB Output is correct
4 Correct 47 ms 17572 KB Output is correct
5 Correct 70 ms 20608 KB Output is correct
6 Correct 65 ms 20684 KB Output is correct
7 Correct 56 ms 20064 KB Output is correct
8 Correct 62 ms 20048 KB Output is correct
9 Correct 66 ms 20720 KB Output is correct
10 Correct 69 ms 20688 KB Output is correct
11 Correct 80 ms 20464 KB Output is correct
12 Correct 67 ms 20696 KB Output is correct
13 Correct 68 ms 20696 KB Output is correct
14 Correct 69 ms 20588 KB Output is correct
15 Correct 66 ms 20556 KB Output is correct
16 Correct 72 ms 20556 KB Output is correct
17 Correct 63 ms 20296 KB Output is correct
18 Correct 72 ms 20532 KB Output is correct
19 Correct 64 ms 20304 KB Output is correct
20 Correct 65 ms 20308 KB Output is correct
21 Correct 67 ms 20308 KB Output is correct
22 Correct 77 ms 20220 KB Output is correct
23 Correct 55 ms 17852 KB Output is correct
24 Correct 56 ms 17984 KB Output is correct
25 Correct 54 ms 18260 KB Output is correct
26 Correct 55 ms 18340 KB Output is correct
27 Correct 66 ms 19156 KB Output is correct
28 Correct 60 ms 19180 KB Output is correct
29 Correct 68 ms 19152 KB Output is correct
30 Correct 66 ms 19252 KB Output is correct
31 Correct 53 ms 18000 KB Output is correct
32 Correct 55 ms 18120 KB Output is correct
33 Correct 54 ms 18328 KB Output is correct
34 Correct 57 ms 18256 KB Output is correct
35 Correct 61 ms 19120 KB Output is correct
36 Correct 59 ms 19028 KB Output is correct
37 Correct 60 ms 19120 KB Output is correct
38 Correct 61 ms 19012 KB Output is correct
39 Correct 61 ms 19244 KB Output is correct
40 Correct 59 ms 19100 KB Output is correct
41 Correct 71 ms 19664 KB Output is correct
42 Correct 63 ms 19796 KB Output is correct
43 Correct 64 ms 19676 KB Output is correct
44 Correct 67 ms 19668 KB Output is correct
45 Correct 63 ms 19680 KB Output is correct
46 Correct 63 ms 19672 KB Output is correct
47 Correct 60 ms 18816 KB Output is correct
48 Correct 59 ms 18904 KB Output is correct
49 Correct 60 ms 18820 KB Output is correct
50 Correct 64 ms 18892 KB Output is correct
51 Correct 54 ms 18040 KB Output is correct
52 Correct 54 ms 18168 KB Output is correct
53 Correct 65 ms 18168 KB Output is correct
54 Correct 57 ms 18200 KB Output is correct
55 Correct 55 ms 18188 KB Output is correct
56 Correct 55 ms 18132 KB Output is correct
57 Correct 55 ms 18236 KB Output is correct
58 Correct 55 ms 18480 KB Output is correct
59 Correct 57 ms 18224 KB Output is correct
60 Correct 54 ms 17876 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17984 KB Output is correct
2 Correct 60 ms 18884 KB Output is correct
3 Correct 12 ms 13056 KB Output is correct
4 Correct 47 ms 17688 KB Output is correct
5 Correct 64 ms 20700 KB Output is correct
6 Correct 65 ms 20556 KB Output is correct
7 Correct 55 ms 20064 KB Output is correct
8 Correct 57 ms 20064 KB Output is correct
9 Correct 66 ms 20668 KB Output is correct
10 Correct 65 ms 20612 KB Output is correct
11 Correct 68 ms 20768 KB Output is correct
12 Correct 70 ms 20684 KB Output is correct
13 Correct 66 ms 20524 KB Output is correct
14 Correct 65 ms 20468 KB Output is correct
15 Correct 67 ms 20628 KB Output is correct
16 Correct 70 ms 20472 KB Output is correct
17 Correct 63 ms 20316 KB Output is correct
18 Correct 62 ms 20312 KB Output is correct
19 Correct 65 ms 20308 KB Output is correct
20 Correct 70 ms 20312 KB Output is correct
21 Correct 72 ms 20212 KB Output is correct
22 Correct 62 ms 20308 KB Output is correct
23 Correct 64 ms 17980 KB Output is correct
24 Correct 53 ms 17808 KB Output is correct
25 Correct 55 ms 18348 KB Output is correct
26 Correct 56 ms 18356 KB Output is correct
27 Correct 63 ms 19284 KB Output is correct
28 Correct 60 ms 19164 KB Output is correct
29 Correct 71 ms 19152 KB Output is correct
30 Correct 67 ms 19268 KB Output is correct
31 Correct 56 ms 17952 KB Output is correct
32 Correct 55 ms 17992 KB Output is correct
33 Correct 59 ms 18344 KB Output is correct
34 Correct 56 ms 18312 KB Output is correct
35 Correct 64 ms 19220 KB Output is correct
36 Correct 59 ms 19084 KB Output is correct
37 Correct 60 ms 19120 KB Output is correct
38 Correct 59 ms 19116 KB Output is correct
39 Correct 60 ms 19092 KB Output is correct
40 Correct 59 ms 19096 KB Output is correct
41 Correct 66 ms 19544 KB Output is correct
42 Correct 69 ms 19776 KB Output is correct
43 Correct 63 ms 19668 KB Output is correct
44 Correct 61 ms 19800 KB Output is correct
45 Correct 61 ms 19908 KB Output is correct
46 Correct 61 ms 19916 KB Output is correct
47 Correct 63 ms 18784 KB Output is correct
48 Correct 64 ms 18944 KB Output is correct
49 Correct 57 ms 18820 KB Output is correct
50 Correct 63 ms 18936 KB Output is correct
51 Correct 54 ms 18196 KB Output is correct
52 Correct 54 ms 18188 KB Output is correct
53 Correct 54 ms 18040 KB Output is correct
54 Correct 53 ms 18200 KB Output is correct
55 Correct 57 ms 18204 KB Output is correct
56 Correct 55 ms 18184 KB Output is correct
57 Correct 56 ms 18216 KB Output is correct
58 Correct 54 ms 18216 KB Output is correct
59 Correct 53 ms 17868 KB Output is correct
60 Correct 54 ms 18100 KB Output is correct