oj.uz

Submission #704392

# Submission time Handle Problem Language Result Execution time Memory
704392 2023-03-02T05:15:56 Z SamNguyen ICC (CEOI16_icc) C++14
7 / 100
 56 ms 480 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
private:
	int n;
	vector<int> sz, par;

public:
	DSU(int n = 0): n(n) {
		sz.assign(n + 1, 1);
		par.assign(n + 1, 0);
		iota(par.begin(), par.end(), 0);
	}

	int root(int u) { return par[u] = (u == par[u] ? u : root(par[u])); }

	bool join(int u, int v) {
		u = root(u), v = root(v);
		if (u == v)
			return false;

		if (sz[u] < sz[v])
			swap(u, v);
		sz[u] += sz[v];
		par[v] = u;
		return true;
	}

	inline bool is_same(int u, int v) {
		return root(u) == root(v);
	}
};

int buffer[2][200];

int query(vector<int> a, vector<int> b) {
	copy(a.begin(), a.end(), buffer[0]);
	copy(b.begin(), b.end(), buffer[1]);
	return query(a.size(), b.size(), buffer[0], buffer[1]);
}

namespace subtask_1 {
	const int N = 15;

	void run() {
		DSU dsu(N);
		for (int t = N - 1; t--; ) {
			[&]() {
				for (int u = 1; u <= N; u++)
				for (int v = u + 1; v <= N; v++) {
					if (not dsu.is_same(u, v) and query({u}, {v})) {
						setRoad(u, v);
						dsu.join(u, v);
						return;
					}
				}
			}();
		}
	}
}

void run(int N) {
	if (N == 15)
		subtask_1::run();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 480 KB Ok! 1015 queries used.
2 Correct 49 ms 480 KB Ok! 1010 queries used.

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 308 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -