oj.uz

Submission #925441

# Submission time Handle Problem Language Result Execution time Memory
925441 2024-02-11T16:12:40 Z adaawf Stray Cat (JOI20_stray) C++14
15 / 100
 3000 ms 22840 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> g[200005];
int f[200005], dx[] = {1, 0, 1, 0, 0, 1}, dd[200005];
vector<int> res;
void dfs(int x, int p) {
    int c = 0;
    for (auto w : g[x]) {
        if (w.second == p) continue;
        c++;
        if (c == 1) {
            for (auto w : g[x]) {
                if (w.second == p) continue;
                res[w.second] = dx[f[x]];
                f[w.first] = (f[x] + 1) % 6;
                dfs(w.first, w.second);
            }
        }
        else {
            for (auto w : g[x]) {
                if (w.second == p) continue;
                if (p == -1) res[w.second] = 0;
                else res[w.second] = res[p] ^ 1;
                if (res[w.second] == 1) f[w.first] = 1;
                else f[w.first] = 2;
                dfs(w.first, w.second);
            }
        }
    }
}
void bfs() {
    queue<int> q;
    q.push(0);
    memset(dd, 0, sizeof dd);
    dd[0] = 1;
    int d = 0;
    while (!q.empty()) {
        int h = q.size();
        for (int i = 0; i < h; i++) {
            int p = q.front();
            q.pop();
            f[p] = d;
            for (auto w : g[p]) {
                if (dd[w.first] == 0) {
                    dd[w.first] = 1;
                    q.push(w.first);
                }
            }
        }
        d++;
    }
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
	res.resize(M);
	for (int i = 0; i < M; i++) {
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	if (A == 2) {
		for (int i = 0; i < N; i++) f[i] = 0;
		dfs(0, -1);
	}
	else {
		bfs();
		for (int i = 0; i < M; i++) {
			res[i] = min(f[U[i]], f[V[i]]) % 3;
		}
	}
	return res;
}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
int A, B, s = 1, flag = 0, k = 0, c = 0;
set<vector<int>> ss = {{1, 0, 1, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 1, 1, 0}, {0, 1, 1, 0, 1}, {1, 1, 0, 1, 0}};
vector<int> v(5, 0);
void Init(int a, int b) {
    A = a;
    B = b;
}
int Move(vector<int> y) {
  	if (A == 2) {
		if (s != 0) {
			s = 0;
			if (y[0] + y[1] != 2) {
				if (min(y[0], y[1]) == 0) {
                    if (y[0] < y[1]) k = 1;
                    else k = 0;
				}
				else {
                    if (y[0] > y[1]) k = 1;
                    else k = 0;
				}
				return k;
			}
			else {
				flag = 1;
                if (y[0] < y[1]) k = 1;
                else k = 0;
				y[k]--;
                if (y[0] < y[1]) v[c++] = 1;
                else v[c++] = 0;
				v[c++] = k;
				return k;
			}
		}
		else {
			if (flag == 0) {
				if (min(y[0], y[1]) == 0) {
                    if (y[0] < y[1]) k = 1;
                    else k = 0;
				}
				else k ^= 1;
				return k;
			}
			else {
				if (y[0] + y[1] != 1) {
					flag = c = 0;
					if (min(y[0], y[1]) == 0) return -1;
                    k ^= 1;
                    return k;
				}
                if (y[0] < y[1]) k = 1;
                else k = 0;
                v[c++] = k;
                if (c == 5) {
                    flag = 0;
                    if (ss.find(v) == ss.end()) {
                        return k;
                    }
                    k = v[3];
                    return -1;
                }
                return k;
			}
		}
  	}
	else {
		vector<int> v;
		for (int i = 0; i < 3; i++) {
            if (y[i] != 0) {
                v.push_back(i);
            }
		}
		if (v.size() == 1) {
            return v[0];
		}
        if (v[0] == 0) {
            if (v[1] == 1) return 0;
            return 2;
        }
        return 1;
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 21644 KB Output is correct
2 Correct 3 ms 7276 KB Output is correct
3 Correct 34 ms 20920 KB Output is correct
4 Correct 40 ms 22840 KB Output is correct
5 Correct 37 ms 22788 KB Output is correct
6 Correct 36 ms 21532 KB Output is correct
7 Correct 44 ms 21504 KB Output is correct
8 Correct 39 ms 22268 KB Output is correct
9 Correct 34 ms 22344 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 21644 KB Output is correct
2 Correct 3 ms 7276 KB Output is correct
3 Correct 34 ms 20920 KB Output is correct
4 Correct 40 ms 22840 KB Output is correct
5 Correct 37 ms 22788 KB Output is correct
6 Correct 36 ms 21532 KB Output is correct
7 Correct 44 ms 21504 KB Output is correct
8 Correct 39 ms 22268 KB Output is correct
9 Correct 34 ms 22344 KB Output is correct
10 Correct 26 ms 19772 KB Output is correct
11 Correct 26 ms 19780 KB Output is correct
12 Correct 26 ms 19788 KB Output is correct
13 Correct 26 ms 19776 KB Output is correct
14 Correct 27 ms 20036 KB Output is correct
15 Correct 32 ms 20280 KB Output is correct
16 Correct 39 ms 22320 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19332 KB Output is correct
2 Correct 2 ms 6932 KB Output is correct
3 Correct 25 ms 18936 KB Output is correct
4 Correct 34 ms 21056 KB Output is correct
5 Correct 34 ms 20800 KB Output is correct
6 Correct 28 ms 19296 KB Output is correct
7 Correct 32 ms 19232 KB Output is correct
8 Correct 30 ms 20052 KB Output is correct
9 Correct 31 ms 20088 KB Output is correct
10 Correct 30 ms 19684 KB Output is correct
11 Correct 28 ms 19800 KB Output is correct
12 Correct 33 ms 19936 KB Output is correct
13 Correct 34 ms 19800 KB Output is correct
14 Correct 31 ms 20008 KB Output is correct
15 Correct 30 ms 20048 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 19332 KB Output is correct
2 Correct 2 ms 6932 KB Output is correct
3 Correct 25 ms 18936 KB Output is correct
4 Correct 34 ms 21056 KB Output is correct
5 Correct 34 ms 20800 KB Output is correct
6 Correct 28 ms 19296 KB Output is correct
7 Correct 32 ms 19232 KB Output is correct
8 Correct 30 ms 20052 KB Output is correct
9 Correct 31 ms 20088 KB Output is correct
10 Correct 30 ms 19684 KB Output is correct
11 Correct 28 ms 19800 KB Output is correct
12 Correct 33 ms 19936 KB Output is correct
13 Correct 34 ms 19800 KB Output is correct
14 Correct 31 ms 20008 KB Output is correct
15 Correct 30 ms 20048 KB Output is correct
16 Correct 24 ms 17736 KB Output is correct
17 Correct 24 ms 17724 KB Output is correct
18 Correct 27 ms 17812 KB Output is correct
19 Correct 31 ms 17772 KB Output is correct
20 Correct 27 ms 18444 KB Output is correct
21 Correct 27 ms 18244 KB Output is correct
22 Correct 30 ms 20292 KB Output is correct
23 Correct 28 ms 17868 KB Output is correct
24 Correct 28 ms 17984 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7108 KB Output is correct
2 Correct 2 ms 6944 KB Output is correct
3 Correct 105 ms 7108 KB Output is correct
4 Correct 3 ms 7196 KB Output is correct
5 Correct 3 ms 7204 KB Output is correct
6 Correct 3 ms 7204 KB Output is correct
7 Correct 3 ms 7204 KB Output is correct
8 Correct 3 ms 7200 KB Output is correct
9 Correct 3 ms 7200 KB Output is correct
10 Correct 3 ms 7204 KB Output is correct
11 Correct 2 ms 7196 KB Output is correct
12 Execution timed out 3045 ms 6492 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 7772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 7768 KB Time limit exceeded
2 Halted 0 ms 0 KB -