oj.uz

Submission #260644

# Submission time Handle Problem Language Result Execution time Memory
260644 2020-08-10T15:55:15 Z amoo_safar Stray Cat (JOI20_stray) C++17
100 / 100
 70 ms 17860 KB 
#include <bits/stdc++.h>
#include "Anthony.h"

#define pb push_back

using namespace std;

typedef pair<int, int> pii;

namespace {

const int N = 2e4 + 10;

int col[N];
vector<pii> G[N];

int pat[] = {0, 1, 0, 0, 1, 1};

void DFS(int u, int p, int pt = 0){
	int cnt = 0;
	for(auto [adj, id] : G[u]){
		if(adj != p) cnt ++;
	}
	if(cnt == 0) return ;
	if(cnt == 1){
		pt = (pt + 1) % 6;
	} else {
		pt = (pat[pt] == 0 ? 1 : 0);
	}
	if(u == 0) pt = 0;


	for(auto [adj, id] : G[u]){
		if(adj != p){
			DFS(adj, u, pt);
			col[id] = pat[pt];
		}
	}
}

}

vector<int> Mark2(int n, int m, int A, int B, vector<int> U, vector<int> V) {
	
	//cerr << "Salam\n";
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	queue<int> Q;
	vector<int> dep(n, 1'000'000'000);
	dep[0] = 0;
	Q.push(0);
	int fr;
	while(!Q.empty()){
		fr = Q.front();
		Q.pop();

		for(auto [adj, id] : G[fr]){
			if(dep[adj] > dep[fr] + 1){
				dep[adj] = dep[fr] + 1;
				Q.push(adj);
			}
		}
	}


	//cerr << "Bye\n";
	vector<int> C(m, 0);
	for(int i = 0; i < m; i++) C[i] = min(dep[U[i]], dep[V[i]]) % 3;
	return C;
}


vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
	if(B == 0){
		return Mark2(n, m, A, B, U, V);
	}
	assert(m == n - 1);
	assert(B >= 6);
	//cerr << "Salam\n";
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	DFS(0, -1);

	//cerr << "Bye\n";
	vector<int> C(m, 0);
	for(int i = 0; i < m; i++) C[i] = col[i];
	return C;
}

#ifdef safar
int main(){
	int n;
	cin >> n;
	vector<int> U1, V1, R;

	int u, v;
	for(int i = 0; i < n - 1; i++){
		cin >> u >> v;
		U1.pb(u);
		V1.pb(v);
	}
	R = Mark(n, n - 1, 2, 6, U1, V1);
	for(auto x : R) cerr << x << '\n';
}
#endif
/*
20 30 3 0 4
1 9
0 11
7 9
2 8
6 13
3 4
6 16
8 14
6 17
10 12
9 13
3 10
13 17
7 12
11 15
9 17
18 19
3 18
10 19
4 18
4 19
2 4
10 18
1 12
3 12
2 3
4 14
2 14
13 15
5 14

*/
#include <bits/stdc++.h>
#include "Catherine.h"

#define pb push_back

using namespace std;

typedef pair<int, int> pii;

namespace {

vector<int> vis, pa;
bool UP = false;


int MoveUp(vector<int> y){
	int deg = (vis.size() > 0 ? 1 : 0);
	for(auto x : y) deg += x;
	//cerr << "% " << deg << '\n';
	if(deg == 1 and !vis.empty()){
		return -1;
	}
	if(deg <= 2){
		for(int i = 0; i < 2; i++)
			if(y[i])
				return i;
	}
	//cerr << "$$ " << y[0] << ' ' << y[1] << '\n';
	int mn = 1'000'000'000;
	for(auto x : y) mn = min(x, mn);
	if(mn == 0) return -1;
	if(vis.empty())
		return (y[0] == 1 ? 0 : 1);
	return 1 - vis.back();
}

int Hand(int x){
	//cerr << "# " << x << '\n';
	if(x == -1) vis.pb(vis.back());
	else vis.pb(x);
	pa.pb(vis.back());

	return x;
}

bool Rev(){
	int sm = 3;
	for(auto x : pa) sm -= x;
	pa.pb(sm);
	for(int i = 0; i < 6; i++) pa.pb(pa[i]);
	for(int i = 0; i + 4 < (int)pa.size(); i ++){
		if((pa[i] == 0) && (pa[i+1] == 0) && (pa[i + 2] == 1) && (pa[i + 3] == 1)){
			return true;
		}
	}
	return false;
}

int state = 0;

int Move2(vector<int> y){
	if(!vis.empty()) y[vis.back()] ++;
	if(y[0] + y[1] == 0) return 2;
	if(y[0] + y[2] == 0) return 1;
	if(y[1] + y[2] == 0) return 0;
	if(y[2] == 0) return 0;
	if(y[0] == 0) return 1;
	if(y[1] == 0) return 2;
	return -1;
}

}  // namespace


void Init(int A, int B){
	if(B == 0) state = 1;
}


int Move(vector<int> y){
	if(state == 1) return Hand(Move2(y));
	//cerr << "O\n";
	int deg = (vis.size() > 0 ? 1 : 0);
	for(auto x : y) deg += x;
	if(deg >= 3) UP = true;
	if(deg == 1) UP = true;
	//cerr << "A\n";
	if(UP) return Hand(MoveUp(y));
	//cerr << "E\n";

	if(vis.empty()){
		int idx;
		for(int i = 0; i < 2; i++) if(y[i]) idx = i;
		y[idx] -= 1;
		int idx2;
		for(int i = 0; i < 2; i++) if(y[i]) idx2 = i;
		
		pa.pb(idx2);
		return Hand(idx);
	}

	if(pa.size() < 4){
		int idx;
		for(int i = 0; i < 2; i++) if(y[i]) idx = i;
		return Hand(idx);
	}
	int idx;
	for(int i = 0; i < 2; i++) if(y[i]) idx = i;
	pa.pb(idx);

	if(Rev()){
		UP = true;
		return Hand(-1);
	}
	UP = true;
	return Hand(MoveUp(y));
}

Compilation message

Anthony.cpp: In function 'void {anonymous}::DFS(int, int, int)':
Anthony.cpp:21:19: warning: unused variable 'id' [-Wunused-variable]
  for(auto [adj, id] : G[u]){
                   ^
Anthony.cpp: In function 'std::vector<int> Mark2(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:20: warning: unused variable 'id' [-Wunused-variable]
   for(auto [adj, id] : G[fr]){
                    ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16244 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 43 ms 15564 KB Output is correct
4 Correct 63 ms 17604 KB Output is correct
5 Correct 65 ms 17860 KB Output is correct
6 Correct 49 ms 16088 KB Output is correct
7 Correct 48 ms 16088 KB Output is correct
8 Correct 58 ms 16912 KB Output is correct
9 Correct 60 ms 16916 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16244 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 43 ms 15564 KB Output is correct
4 Correct 63 ms 17604 KB Output is correct
5 Correct 65 ms 17860 KB Output is correct
6 Correct 49 ms 16088 KB Output is correct
7 Correct 48 ms 16088 KB Output is correct
8 Correct 58 ms 16912 KB Output is correct
9 Correct 60 ms 16916 KB Output is correct
10 Correct 49 ms 14164 KB Output is correct
11 Correct 45 ms 14228 KB Output is correct
12 Correct 55 ms 14140 KB Output is correct
13 Correct 52 ms 14228 KB Output is correct
14 Correct 48 ms 14412 KB Output is correct
15 Correct 53 ms 14796 KB Output is correct
16 Correct 57 ms 17084 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13804 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 13436 KB Output is correct
4 Correct 66 ms 15412 KB Output is correct
5 Correct 63 ms 15188 KB Output is correct
6 Correct 46 ms 13792 KB Output is correct
7 Correct 46 ms 13796 KB Output is correct
8 Correct 55 ms 14616 KB Output is correct
9 Correct 55 ms 14564 KB Output is correct
10 Correct 57 ms 14336 KB Output is correct
11 Correct 53 ms 14276 KB Output is correct
12 Correct 63 ms 14372 KB Output is correct
13 Correct 55 ms 14164 KB Output is correct
14 Correct 60 ms 14732 KB Output is correct
15 Correct 59 ms 14648 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13804 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 40 ms 13436 KB Output is correct
4 Correct 66 ms 15412 KB Output is correct
5 Correct 63 ms 15188 KB Output is correct
6 Correct 46 ms 13792 KB Output is correct
7 Correct 46 ms 13796 KB Output is correct
8 Correct 55 ms 14616 KB Output is correct
9 Correct 55 ms 14564 KB Output is correct
10 Correct 57 ms 14336 KB Output is correct
11 Correct 53 ms 14276 KB Output is correct
12 Correct 63 ms 14372 KB Output is correct
13 Correct 55 ms 14164 KB Output is correct
14 Correct 60 ms 14732 KB Output is correct
15 Correct 59 ms 14648 KB Output is correct
16 Correct 48 ms 12228 KB Output is correct
17 Correct 46 ms 12236 KB Output is correct
18 Correct 45 ms 12316 KB Output is correct
19 Correct 44 ms 12316 KB Output is correct
20 Correct 51 ms 12996 KB Output is correct
21 Correct 51 ms 12708 KB Output is correct
22 Correct 54 ms 14900 KB Output is correct
23 Correct 44 ms 12448 KB Output is correct
24 Correct 44 ms 12444 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 1552 KB Output is correct
4 Correct 3 ms 2048 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 2 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 1856 KB Output is correct
15 Correct 2 ms 1600 KB Output is correct
16 Correct 2 ms 1536 KB Output is correct
17 Correct 2 ms 1792 KB Output is correct
18 Correct 2 ms 1536 KB Output is correct
19 Correct 2 ms 1792 KB Output is correct
20 Correct 2 ms 1792 KB Output is correct
21 Correct 2 ms 1536 KB Output is correct
22 Correct 2 ms 1792 KB Output is correct
23 Correct 2 ms 1792 KB Output is correct
24 Correct 2 ms 1536 KB Output is correct
25 Correct 2 ms 1792 KB Output is correct
26 Correct 2 ms 1792 KB Output is correct
27 Correct 2 ms 1792 KB Output is correct
28 Correct 2 ms 1792 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11828 KB Output is correct
2 Correct 50 ms 13180 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 38 ms 11432 KB Output is correct
5 Correct 58 ms 14672 KB Output is correct
6 Correct 61 ms 14680 KB Output is correct
7 Correct 47 ms 13780 KB Output is correct
8 Correct 47 ms 13652 KB Output is correct
9 Correct 67 ms 14632 KB Output is correct
10 Correct 69 ms 14684 KB Output is correct
11 Correct 63 ms 14676 KB Output is correct
12 Correct 69 ms 14540 KB Output is correct
13 Correct 58 ms 14668 KB Output is correct
14 Correct 56 ms 14684 KB Output is correct
15 Correct 57 ms 14680 KB Output is correct
16 Correct 62 ms 14620 KB Output is correct
17 Correct 55 ms 14200 KB Output is correct
18 Correct 66 ms 14284 KB Output is correct
19 Correct 53 ms 14296 KB Output is correct
20 Correct 53 ms 14300 KB Output is correct
21 Correct 61 ms 14304 KB Output is correct
22 Correct 66 ms 14688 KB Output is correct
23 Correct 44 ms 11880 KB Output is correct
24 Correct 46 ms 11860 KB Output is correct
25 Correct 47 ms 12496 KB Output is correct
26 Correct 46 ms 12372 KB Output is correct
27 Correct 51 ms 13328 KB Output is correct
28 Correct 60 ms 13300 KB Output is correct
29 Correct 55 ms 13300 KB Output is correct
30 Correct 54 ms 13260 KB Output is correct
31 Correct 43 ms 11876 KB Output is correct
32 Correct 46 ms 11860 KB Output is correct
33 Correct 43 ms 12240 KB Output is correct
34 Correct 45 ms 12480 KB Output is correct
35 Correct 56 ms 13292 KB Output is correct
36 Correct 49 ms 13124 KB Output is correct
37 Correct 51 ms 13264 KB Output is correct
38 Correct 48 ms 13264 KB Output is correct
39 Correct 58 ms 13260 KB Output is correct
40 Correct 52 ms 13392 KB Output is correct
41 Correct 54 ms 13804 KB Output is correct
42 Correct 55 ms 13760 KB Output is correct
43 Correct 70 ms 13780 KB Output is correct
44 Correct 59 ms 13812 KB Output is correct
45 Correct 59 ms 13816 KB Output is correct
46 Correct 56 ms 13772 KB Output is correct
47 Correct 55 ms 13096 KB Output is correct
48 Correct 53 ms 13096 KB Output is correct
49 Correct 48 ms 12884 KB Output is correct
50 Correct 56 ms 13080 KB Output is correct
51 Correct 47 ms 12344 KB Output is correct
52 Correct 43 ms 12212 KB Output is correct
53 Correct 43 ms 12220 KB Output is correct
54 Correct 44 ms 12216 KB Output is correct
55 Correct 44 ms 12232 KB Output is correct
56 Correct 44 ms 12148 KB Output is correct
57 Correct 44 ms 12240 KB Output is correct
58 Correct 43 ms 12248 KB Output is correct
59 Correct 44 ms 12128 KB Output is correct
60 Correct 45 ms 12004 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11868 KB Output is correct
2 Correct 49 ms 13052 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 37 ms 11444 KB Output is correct
5 Correct 57 ms 14548 KB Output is correct
6 Correct 56 ms 14868 KB Output is correct
7 Correct 46 ms 13656 KB Output is correct
8 Correct 47 ms 13748 KB Output is correct
9 Correct 61 ms 14676 KB Output is correct
10 Correct 61 ms 14800 KB Output is correct
11 Correct 56 ms 14676 KB Output is correct
12 Correct 58 ms 14676 KB Output is correct
13 Correct 57 ms 14692 KB Output is correct
14 Correct 59 ms 14668 KB Output is correct
15 Correct 57 ms 14672 KB Output is correct
16 Correct 65 ms 14676 KB Output is correct
17 Correct 56 ms 14288 KB Output is correct
18 Correct 56 ms 14292 KB Output is correct
19 Correct 56 ms 14296 KB Output is correct
20 Correct 63 ms 14292 KB Output is correct
21 Correct 56 ms 14584 KB Output is correct
22 Correct 62 ms 14296 KB Output is correct
23 Correct 44 ms 12024 KB Output is correct
24 Correct 46 ms 11888 KB Output is correct
25 Correct 48 ms 12260 KB Output is correct
26 Correct 46 ms 12368 KB Output is correct
27 Correct 52 ms 13312 KB Output is correct
28 Correct 54 ms 13440 KB Output is correct
29 Correct 50 ms 13308 KB Output is correct
30 Correct 52 ms 13296 KB Output is correct
31 Correct 45 ms 11884 KB Output is correct
32 Correct 43 ms 11888 KB Output is correct
33 Correct 45 ms 12492 KB Output is correct
34 Correct 48 ms 12492 KB Output is correct
35 Correct 53 ms 13304 KB Output is correct
36 Correct 51 ms 13392 KB Output is correct
37 Correct 56 ms 13260 KB Output is correct
38 Correct 54 ms 13524 KB Output is correct
39 Correct 51 ms 13388 KB Output is correct
40 Correct 50 ms 13392 KB Output is correct
41 Correct 52 ms 13812 KB Output is correct
42 Correct 57 ms 14064 KB Output is correct
43 Correct 52 ms 14036 KB Output is correct
44 Correct 54 ms 13772 KB Output is correct
45 Correct 55 ms 13780 KB Output is correct
46 Correct 53 ms 13804 KB Output is correct
47 Correct 48 ms 13096 KB Output is correct
48 Correct 49 ms 13084 KB Output is correct
49 Correct 46 ms 12884 KB Output is correct
50 Correct 50 ms 13132 KB Output is correct
51 Correct 43 ms 11988 KB Output is correct
52 Correct 50 ms 12208 KB Output is correct
53 Correct 47 ms 12220 KB Output is correct
54 Correct 48 ms 12116 KB Output is correct
55 Correct 44 ms 12220 KB Output is correct
56 Correct 44 ms 12212 KB Output is correct
57 Correct 45 ms 12236 KB Output is correct
58 Correct 50 ms 12236 KB Output is correct
59 Correct 46 ms 12004 KB Output is correct
60 Correct 45 ms 11988 KB Output is correct