oj.uz

Submission #84214

# Submission time Handle Problem Language Result Execution time Memory
84214 2018-11-13T21:40:28 Z MatheusLealV Pictionary (COCI18_pictionary) C++17
56 / 140
 55 ms 16632 KB 
#include <bits/stdc++.h>
#define inf (2000000000)
#define N 100050
#define logn 20
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

struct E
{
	int a, b, c;

} A[N];

bool cmp(E A, E B) {
	return A.c > B.c;
}

int n, m, q, id, pai[N], peso[N], nivel[N], anc[N][logn], best[N][logn];

vector<pii> grafo[N], all[N];

void dfs(int x, int p)
{
	nivel[x] = nivel[p] + 1;

	anc[x][0] = p;

	for(auto v: grafo[x])
	{
		if(v.f == p) continue;

		dfs(v.f, x);

		best[v.f][0] = v.s;
	}
}

int query(int u, int v)
{
	if(nivel[u] < nivel[v]) swap(u, v);

	int resp = m;

	for(int i = logn - 1; i >= 0; i--)
		if(nivel[u] - (1<<i) >= nivel[v])
			resp = min(resp, best[u][i]), u = anc[u][i];

	if(u == v) return resp;

	for(int i = logn - 1; i >= 0; i--)
		if(anc[u][i] != -1 && anc[u][i] != anc[v][i])
			resp = min(min(resp, best[u][i]), best[v][i]), u = anc[u][i], v = anc[v][i];

	return min(min(resp, best[u][0]), best[v][0]);
}

int Find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
	a = Find(a), b = Find(b);

	if(a == b) return;

	if(peso[a] > peso[b]) pai[b] = a;

	else if(peso[a] < peso[b]) pai[a] = b;

	else pai[a] = b, peso[b] ++;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m>>q;

	for(int i = m; i >= 1; i--)
	{
		for(int j = 1; i * j <= n; j++)
		{
			++id;

			A[id] = {i, i*j, i};
		}
	}

	sort(A + 1, A + id + 1, cmp);

	for(int i = 1; i <= n; i++) pai[i] = i;

	for(int i = 1; i <= id; i++)
	{
		int u = A[i].a, v = A[i].b, c = A[i].c;

		if(Find(u) == Find(v)) continue;

		join(u, v);

		grafo[u].push_back({v, c});

		grafo[v].push_back({u, c});
	}

	memset(anc, -1, sizeof anc);

	dfs(1, 1);

	for(int j = 1; j < logn; j++)
	{
		for(int i = 1; i <= n; i++)
		{
			if(anc[i][j-1] != -1) anc[i][j] = anc[anc[i][j - 1]][j-1];//anc[anc[i][j - 1]][j - 1];

			if(anc[i][j - 1] != -1) best[i][j] = min(best[anc[i][j - 1]][j - 1], best[i][j - 1]);
		}
	}

	for(int i = 1, u, v; i <= q; i++)
	{
		cin>>u>>v;

		int ans = query(u, v);

		cout<<m - ans + 1<<'\n';
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13048 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 13348 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14208 KB Output is correct
2 Correct 41 ms 14768 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15884 KB Output is correct
2 Correct 53 ms 16632 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 16632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -