oj.uz

Submission #867535

# Submission time Handle Problem Language Result Execution time Memory
867535 2023-10-28T15:35:50 Z pizzamoeger popa (BOI18_popa) C++14
100 / 100
 51 ms 676 KB 
#include <bits/stdc++.h>
#include "popa.h"
#define ll long long
 
using namespace std;
 
int quuu(int a, int b, int c, int d, int N) {
  assert(a >= 0 && a < N);
  assert(b >= 0 && b < N);
  if (a > b) swap(a, b);
  assert(c >= 0 && c < N);
  assert(d >= 0 && d < N);
  if (c > d) swap(c, d);
  return query(a, b, c, d);
}
 
int solve(int N, int* Left, int* Right) {
	vector<int> parent (N, -1);
	
	for (int i = 0; i < N; i++) {
		Left[i] = -1;
		Right[i] = -1;
	}
 
	int rl = 0;
	for (int i = 1; i < N; i++) {
		int v = rl;
		while(parent[v] != -1 && quuu(i, i, i, v, N) == 1) {
			v = parent[v];
		}
 
		if (parent[v] == -1) {
			if (quuu(i, i, i, v, N)) {
				parent[v] = i;
				Left[i] = v;
				rl = i;
			} else {
				parent[i] = v;
				Left[i] = Right[v];
				Right[v] = i;
				rl = i;
			}
		} else {
			parent[i] = v;
			Left[i] = Right[v];
			Right[v] = i;
			rl = i;
		}
	}
 
	int root = rl;
	while (parent[root] != -1) root = parent[root];
	return root;
}
 
/*signed main() {
	const int N = 6;
	int* Left = new int[N];
	int* Right = new int[N];
	int ret = solve(N, Left, Right);
	cerr << ret;
 
	for (int i = 0; i < N; i++) {
		cout << Left[i] << " " << Right[i] << "\n";
	}
 
	return 0;
}*/

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 424 KB Output is correct
2 Correct 40 ms 428 KB Output is correct
3 Correct 25 ms 448 KB Output is correct
4 Correct 39 ms 676 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 448 KB Output is correct
2 Correct 43 ms 448 KB Output is correct
3 Correct 44 ms 452 KB Output is correct
4 Correct 42 ms 448 KB Output is correct