oj.uz

Submission #1012922

# Submission time Handle Problem Language Result Execution time Memory
1012922 2024-07-02T20:08:51 Z Ivo_12 Stray Cat (JOI20_stray) C++17
20 / 100
 41 ms 17464 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

namespace {

const int N = 2e4+10, M = 2e4+10, A = 4;

vector < pii > edges[N];
vector < int > oznake;
int dis[N];
int zap[N];
queue < int > q;

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

vector < int > mark( int n, int m, int a, int b, vector < int > t1, vector < int > t2 ) {
	for(int i = 0; i < m; i++) {
		edges[t1[i]].pb(mp(t2[i], i));
		edges[t2[i]].pb(mp(t1[i], i));
		oznake.pb(-1);
	}
	dis[0] = 1;
	q.push(0);
	int cur;
	int sus;
	while(!q.empty()) {
		cur = q.front();
		q.pop();
		for(int i = 0; i < (int) edges[cur].size(); i++) {
			sus = edges[cur][i].F;
			if(dis[sus] == 0) {
				q.push(sus);
				dis[sus] = dis[cur]+1;
			}
		}
	}
	if(a>=3) {
		q.push(0);
		while(!q.empty()) {
			cur = q.front();
			q.pop();
			for(int i = 0; i < (int) edges[cur].size(); i++) {
				sus = edges[cur][i].F;
				if(oznake[edges[cur][i].S] == -1) {
					if(dis[sus] > dis[cur]) q.push(sus);
					oznake[edges[cur][i].S] = (dis[cur] - 1) % 3;
				}
			}
		}
	}
	else {
		q.push(0);
		while(!q.empty()) {
			cur = q.front();
			q.pop();
			for(int i = 0; i < (int) edges[cur].size(); i++) {
				sus = edges[cur][i].F;
				if(oznake[edges[cur][i].S] == -1 && (int) edges[cur].size() > 2) {
					if(dis[sus] > dis[cur]) q.push(sus);
					oznake[edges[cur][i].S] = (pat[zap[cur]%6] + 1) % 2;
					zap[sus] = (pat[zap[cur]] + 1) % 2;
				}
				if(oznake[edges[cur][i].S] == -1 && ((int) ((int) edges[cur].size() == 2 && cur != 0) || ((int) edges[cur].size() == 1 && cur == 0))) {
					if(dis[sus] > dis[cur]) q.push(sus);
					oznake[edges[cur][i].S] = pat[(zap[cur] + 1)%6];
					zap[sus] = zap[cur] + 1;
				}
			}
		}
	}
	
	return oznake;
}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  std::vector<int> X(M);
  return ::mark(N, M, A, B, U, V);
}
#include "Catherine.h"
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

namespace {

int ga, gb;
int l[2];

int revpatt[6] = {1, 1, 0, 0, 1, 0};
vector < int > patt[6];
vector < int > ori;
int pokusaj = 0;


void init( int a, int b ) {
	ga = a;
	gb = b;
	l[0] = 0;
	l[1] = 0;
	for(int i = 0; i < 6; i++) {
		for(int j = 0; j < 5; j++) {
			patt[i].pb(revpatt[(j+i)%6]);
		}
	}
}

int move( vector < int > v ) {
	
	if(::ga>=3) {
		if(v[0] && v[1]) return 0;
		if(v[2] && v[0]) return 2;
		if(v[1] && v[2]) return 1;
		if(!(v[0] || v[1])) return 2;
		if(!(v[2] || v[0])) return 1;
		if(!(v[1] || v[2])) return 0;
	}
	pokusaj++;
	if(pokusaj == 1 && v[0] + v[1] == 2) {
		if(v[0] == 1 && v[1] == 1) {
			ori.pb(0);
			ori.pb(1);
			l[0] = 0;
			l[1] = 1;
			return 1;
		}
		if(v[0] == 2 && v[1] == 0) {
			ori.pb(0);
			ori.pb(0);
			l[0] = 1;
			l[1] = 0;
			return 0;
		}
		if(v[0] == 0 && v[1] == 2) {
			ori.pb(1);
			ori.pb(1);
			l[0] = 0;
			l[1] = 1;
			return 1;
		}
	}
	else {
		if((pokusaj == 2 || pokusaj == 3) && v[0] + v[1] == 1) {
			ori.pb((int) (v[0] == 0));
			l[0] = v[0] == 1;
			l[1] = v[1] == 1;
			return ((int) (v[0] == 0));
		}
		else {
			if((pokusaj == 4) && v[0] + v[1] == 1) {
				ori.pb((int) (v[0] == 0));
				for(int i = 0; i < 6; i++) if(ori==patt[i]) return -1;
				l[0] = v[0] == 1;
				l[1] = v[1] == 1;
				return (int) (v[0] == 0);
			}
			else pokusaj = 10;
		}
	}
	pokusaj = 10;
	if(v[0] == 0 && v[1] == 0) return -1;
	if(v[0] == 0 && v[1] > 1) {
		return -1;
	}
	if(v[0] > 1 && v[1] == 0) {
		return -1;
	}
	if(v[0] == 0 && v[1] == 1) {
		l[1] = 1;
		l[0] = 0;
		return 1;
	}
	if(v[0] == 1 && v[1] == 0) {
		l[1] = 0;
		l[0] = 1;
		return 0;
	}
	if(v[0] == 1 && v[1] > 1) {
		l[1] = 0;
		l[0] = 1;
		return 0;
	}
	if(v[0] > 1 && v[1] == 1) {
		l[1] = 1;
		l[0] = 0;
		return 1;
	}
	if(l[0]) {
		l[1] = 1;
		l[0] = 0;
		return 1;
	}
	if(l[1]) {
		l[1] = 0;
		l[0] = 1;
		return 0;
	}
	if(v[0] > v[1]) {
		l[1] = 1;
		l[0] = 0;
		return 1;
	}
	l[1] = 0;
	l[0] = 1;
	return 0;
	
}

}  // namespace

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

int Move(std::vector<int> y) {
	return ::move(y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16472 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 23 ms 15680 KB Output is correct
4 Correct 41 ms 17420 KB Output is correct
5 Correct 35 ms 17464 KB Output is correct
6 Correct 26 ms 16216 KB Output is correct
7 Correct 26 ms 16212 KB Output is correct
8 Correct 30 ms 16988 KB Output is correct
9 Correct 33 ms 16828 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16472 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 23 ms 15680 KB Output is correct
4 Correct 41 ms 17420 KB Output is correct
5 Correct 35 ms 17464 KB Output is correct
6 Correct 26 ms 16216 KB Output is correct
7 Correct 26 ms 16212 KB Output is correct
8 Correct 30 ms 16988 KB Output is correct
9 Correct 33 ms 16828 KB Output is correct
10 Correct 26 ms 14416 KB Output is correct
11 Correct 25 ms 14176 KB Output is correct
12 Correct 27 ms 14392 KB Output is correct
13 Correct 25 ms 14144 KB Output is correct
14 Correct 25 ms 14680 KB Output is correct
15 Correct 31 ms 14932 KB Output is correct
16 Correct 30 ms 17100 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13912 KB Output is correct
2 Correct 1 ms 1300 KB Output is correct
3 Correct 22 ms 13380 KB Output is correct
4 Correct 30 ms 15408 KB Output is correct
5 Correct 34 ms 15232 KB Output is correct
6 Correct 25 ms 13924 KB Output is correct
7 Correct 31 ms 13916 KB Output is correct
8 Correct 34 ms 14712 KB Output is correct
9 Correct 28 ms 14740 KB Output is correct
10 Correct 26 ms 14432 KB Output is correct
11 Correct 30 ms 14396 KB Output is correct
12 Correct 26 ms 14416 KB Output is correct
13 Correct 31 ms 14356 KB Output is correct
14 Correct 28 ms 14600 KB Output is correct
15 Correct 27 ms 14664 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13912 KB Output is correct
2 Correct 1 ms 1300 KB Output is correct
3 Correct 22 ms 13380 KB Output is correct
4 Correct 30 ms 15408 KB Output is correct
5 Correct 34 ms 15232 KB Output is correct
6 Correct 25 ms 13924 KB Output is correct
7 Correct 31 ms 13916 KB Output is correct
8 Correct 34 ms 14712 KB Output is correct
9 Correct 28 ms 14740 KB Output is correct
10 Correct 26 ms 14432 KB Output is correct
11 Correct 30 ms 14396 KB Output is correct
12 Correct 26 ms 14416 KB Output is correct
13 Correct 31 ms 14356 KB Output is correct
14 Correct 28 ms 14600 KB Output is correct
15 Correct 27 ms 14664 KB Output is correct
16 Correct 23 ms 12420 KB Output is correct
17 Correct 20 ms 12368 KB Output is correct
18 Correct 23 ms 12376 KB Output is correct
19 Correct 24 ms 12380 KB Output is correct
20 Correct 26 ms 13072 KB Output is correct
21 Correct 26 ms 12732 KB Output is correct
22 Correct 27 ms 14944 KB Output is correct
23 Correct 22 ms 12616 KB Output is correct
24 Correct 22 ms 12620 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12120 KB Output is correct
2 Incorrect 24 ms 12372 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12120 KB Output is correct
2 Incorrect 23 ms 12468 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -