oj.uz

Submission #40398

# Submission time Handle Problem Language Result Execution time Memory
40398 2018-01-31T13:16:47 Z szawinis Pictionary (COCI18_pictionary) C++14
140 / 140
 430 ms 27188 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+2;

int n, m, q, a[N], b[N], l[N], r[N], dsu[N];
vector<int> ls[N];
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}
int main() {
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 0; i < q; i++) cin >> a[i] >> b[i];
	fill(l, l+q, 0);
	fill(r, r+q, m);
	for(int iter = 18; iter >= 0; iter--) {
		for(int i = 0; i < q; i++) if(l[i] < r[i])
			ls[m - (l[i] + r[i] >> 1) + 1].push_back(i);

		fill(dsu+1, dsu+n+1, -1);
		for(int i: ls[m+1]) {
			int mid = l[i] + r[i] >> 1;
			if(root(a[i]) != root(b[i])) l[i] = mid+1;
			else r[i] = mid;
		}
		ls[m+1].clear();
		for(int x = m; x >= 1; x--) {
			for(int y = 2*x; y <= n; y += x) merge(x, y);
			for(int i: ls[x]) {
				int mid = l[i] + r[i] >> 1;
				if(root(a[i]) != root(b[i])) l[i] = mid+1;
				else r[i] = mid;
			}
			ls[x].clear();
		}
	}
	for(int i = 0; i < q; i++) printf("%d\n", l[i]);
}

Compilation message

pictionary.cpp: In function 'int main()':
pictionary.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    ls[m - (l[i] + r[i] >> 1) + 1].push_back(i);
                 ^
pictionary.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l[i] + r[i] >> 1;
                   ^
pictionary.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l[i] + r[i] >> 1;
                    ^
pictionary.cpp:15:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
                               ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3064 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4024 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7836 KB Output is correct
2 Correct 60 ms 7836 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 11048 KB Output is correct
2 Correct 84 ms 11048 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 11048 KB Output is correct
2 Correct 126 ms 11148 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 12588 KB Output is correct
2 Correct 111 ms 12588 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 16108 KB Output is correct
2 Correct 175 ms 16108 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 16108 KB Output is correct
2 Correct 280 ms 20068 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 22876 KB Output is correct
2 Correct 350 ms 22876 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 430 ms 27188 KB Output is correct
2 Correct 399 ms 27188 KB Output is correct