Submission #1236860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236860		y0usef	Pictionary (COCI18_pictionary)	C++20	140 / 140	152 ms	10248 KiB

pictionary

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define ull unsigned long long
#define int long long
#define pb push_back
#define pf push_front
#define inpt freopen("input.txt", "r", stdin)
#define outpt freopen("output.txt", "w", stdout)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define EPS 1e-6
#define PI acos(-1)

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OrderedSet;

int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
int dy[8] = {1, 0, 0, -1, 1, -1, 1, -1};

const int N = 3e5 + 10, MOD = 998244353, INF = 3e15, LOG = 23, SQ = 320; // SQ = 317 for 1e5, 448 for 2e5

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

public:
	DSU(int n) : Set(n + 1), sz(n + 1, 1) {
		for(int i = 1; i <= n; i++) Set[i] = i;
	}

	int find(int x) { return Set[x] == x ? x : (Set[x] = find(Set[x])); }
	int get_size(int x) { return sz[find(x)]; }

	void unite(int u, int v) {
		u = find(u);
		v = find(v);
		if(u == v) return;

		if(sz[u] < sz[v]) swap(u, v);
		sz[u] += sz[v];
		Set[v] = u;
	}

	bool connected(int x, int y) { return find(x) == find(y); }
};

struct query {
	int u, v;
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q;
	cin >> n >> m >> q;

	vector<query> queries(q + 1);
	for(int i = 1; i <= q; i++) cin >> queries[i].u >> queries[i].v;

	int l[q + 1], r[q + 1];
	for(int i = 1; i <= q; i++) l[i] = 1, r[i] = m;
	vector<int> ans(q + 1, INF);

	while(true) {
		bool ok = false;
		vector<int> qry[m + 1];
		for(int i = 1; i <= q; i++) {
			if(l[i] > r[i]) continue;
			ok = true;
			qry[l[i] + (r[i] - l[i]) / 2].push_back(i);
		}

		if(!ok) break;

		DSU dsu(n);
		for(int i = 1; i <= m; i++) {
			for(int j = m - i + 1; j <= n; j += m - i + 1) dsu.unite(m - i + 1, j);
			for(auto x : qry[i]) {
				if(dsu.connected(queries[x].u, queries[x].v)) {
					ans[x] = min(ans[x], i);
					r[x] = i - 1;
				}
				else l[x] = i + 1;
			}
		}
	}

	for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14