Submission #704392

#	Time	Username	Problem	Language	Result	Execution time	Memory
704392		SamNguyen	ICC (CEOI16_icc)	C++14	7 / 100	56 ms	480 KiB

icc

#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 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10