Submission #57189

#	Time	Username	Problem	Language	Result	Execution time	Memory
57189		polyfish	Pictionary (COCI18_pictionary)	C++14	140 / 140	313 ms	42604 KiB

pictionary

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;
const int LG_N = 19;
const int INF = 1e9;

class disjoint_set {
public:
	int lab[MAX_N];

	disjoint_set() {
		memset(lab, 0, sizeof(lab));
	}

	int findset(int u) {
		return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
	}

	bool uni(int s, int t) {
		s = findset(s);
		t = findset(t);
		if (s==t)
			return false;
		if (lab[s]<lab[t])
			lab[t] = s;
		else if (lab[s]>lab[t])
			lab[s] = t;
		else {
			lab[s] = t;
			--lab[t];
		}
		return true;
	}
};

struct edge {
	int u, v, w;

	edge() {}
	edge(int u, int v, int w): 
		u(u), v(v), w(w) {}

	bool operator<(const edge &E) {
		return w > E.w;
	}
};

int n, m, nQuery, p[LG_N+2][MAX_N], min_edge[LG_N+2][MAX_N], l[MAX_N];
vector<edge> e;
vector<pair<int, int> > g[MAX_N];
disjoint_set dsu;

void sieve() {
	for (int i=1; i<=m; ++i) {
		for (int j=2*i; j<=n; j += i)
			e.push_back(edge(i, j, i));
	}
}

void process_edge(edge e) {
	if (dsu.uni(e.u, e.v)) {
		g[e.u].push_back(make_pair(e.v, e.w));
		g[e.v].push_back(make_pair(e.u, e.w));
	}
}

void build_MST() {
	sort(e.begin(), e.end());
	// for (int i=0; i<e.size(); ++i)
	// 	cerr << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';
	for (int i=0; i<e.size(); ++i)
		process_edge(e[i]);
}

void fix_root(int u) {
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i].first, w = g[u][i].second;
		if (v!=p[0][u]) {
			p[0][v] = u;
			min_edge[0][v] = w;
			l[v] = l[u] + 1;
			fix_root(v);
		}
	}
}

void init_lca() {
	for (int i=1; i<=LG_N; ++i) {
		for (int j=1; j<=n; ++j) {
			p[i][j] = p[i-1][p[i-1][j]];
			min_edge[i][j] = min(min_edge[i-1][j], min_edge[i-1][p[i-1][j]]);
		}
	}
}

int get_min(int x, int y) {
	int res = INF;
	for (int k=LG_N; k>=0; --k) {
		if (l[p[k][x]]>=l[y]) {
			res = min(res, min_edge[k][x]);
			x = p[k][x];
		}
	}
	for (int k=LG_N; k>=0; --k) {
		if (l[p[k][y]]>=l[x]) {
			res = min(res, min_edge[k][y]);
			y = p[k][y];
		}
	}
	for (int k=LG_N; k>=0; --k) {
		if (p[k][x]!=p[k][y]) {
			res = min(res, min(min_edge[k][x], min_edge[k][y]));
			x = p[k][x];
			y = p[k][y];
		}
	}
	while (x!=y) {
		res = min(res, min(min_edge[0][x], min_edge[0][y]));
		x = p[0][x];
		y = p[0][y];
	}
	return res;
}

void solve_query() {
	while (nQuery--) {
		int u, v;
		cin >> u >> v;
		cout << m - get_min(u, v) + 1 << '\n';
	}
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> nQuery;
	sieve();
	build_MST();
	l[1] = 1;
	fix_root(1);
	init_lca();
	solve_query();
}

Compilation message (stderr)

pictionary.cpp: In function 'void build_MST()':
pictionary.cpp:80:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<e.size(); ++i)
                ~^~~~~~~~~
pictionary.cpp: In function 'void fix_root(int)':
pictionary.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~

• 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