oj.uz

Submission #233285

# Submission time Handle Problem Language Result Execution time Memory
233285 2020-05-20T08:39:31 Z NONAME Tenis (COI19_tenis) C++17
18 / 100
 500 ms 7992 KB 
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef long double ld;

int n, q, pos[3][N], a[3][N];
bool mk[N];

bool f(int v) {
	set <int> s;

	fill(mk, mk + n, 0);

	queue <int> q;
	q.push(v);

//	for (int i = 0; i < 3; i++, cerr << el)
//    for (int j = 0; j < n; j++)
//        cerr << a[i][j] + 1 << ' ';
//    cerr << el;

    while (!q.empty()) {
        s.clear();

		int v = q.front();
		q.pop();
		mk[v] = 1;

		for (int t = 0; t < 3; t++)
		for (int i = pos[t][v] + 1; i < n; i++) {
			int x = a[t][i];

            if (mk[x])
				break;

			s.insert(x);
		}

		for (int x : s)
			mk[x] = 1, q.push(x);
    }

    bool ok = 1;

    for (int i = 0; i < n; i++)
		ok &= mk[i];

	return ok;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    in("input.txt");

	cin >> n >> q;
	for (int t = 0; t < 3; t++)
	for (int i = 0; i < n; i++) {
		cin >> a[t][i];
		a[t][i]--;

        pos[t][a[t][i]] = i;
	}

	while (q--) {
		int type;
		cin >> type;

		if (type == 1) {
			int x;
			cin >> x;
			x--;

			bool ok = f(x);

			cout << ((ok) ? "DA" : "NE") << el;
		}

		if (type == 2) {
            int x, y, z;
            cin >> x >> y >> z;
            x--; y--; z--;

            swap(pos[x][y], pos[x][z]);
			swap(a[x][pos[x][y]], a[x][pos[x][z]]);
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 151 ms 4940 KB Output is correct
14 Correct 109 ms 4024 KB Output is correct
15 Correct 318 ms 7544 KB Output is correct
16 Correct 356 ms 7136 KB Output is correct
17 Execution timed out 868 ms 7992 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 151 ms 4940 KB Output is correct
14 Correct 109 ms 4024 KB Output is correct
15 Correct 318 ms 7544 KB Output is correct
16 Correct 356 ms 7136 KB Output is correct
17 Execution timed out 868 ms 7992 KB Time limit exceeded
18 Halted 0 ms 0 KB -