oj.uz

Submission #240619

# Submission time Handle Problem Language Result Execution time Memory
240619 2020-06-20T09:39:23 Z vanic Pictionary (COCI18_pictionary) C++14
56 / 140
 1500 ms 5888 KB 
#include <iostream>
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string.h>
#include <array>
#include <bitset>
#include <time.h>
#include <cstdlib>

using namespace std;

const int maxn=1e5+5;

int n, m, q;
vector < pair < int, int > > parent[maxn];

int binary(int x, int val){
	int lo=0, hi=parent[x].size()-1, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(parent[x][mid].first>val){
			hi=mid-1;
		}
		else{
			lo=mid;
		}
	}
	return lo;
}

int find(int x, int val){
	int pos=binary(x, val);
	if(parent[x][pos].second==x){
		return x;
	}
	return find(parent[x][pos].second, val);
}

void update(int x, int y, int val){
	x=find(x, val);
	y=find(y, val);
	if(rand()%2){
		swap(x, y);
	}
	parent[x].push_back({val, y});
}

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


int binary2(int x, int y){
	int lo=1, hi=m, mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		if(!query(x, y, mid)){
			lo=mid+1;
		}
		else{
			hi=mid;
		}
	}
	return lo;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	cin >> n >> m >> q;
	for(int i=1; i<=n; i++){
		parent[i].push_back({0, i});
	}
	int br=1;
	for(int i=0; i<m; i++){
		for(int j=(m-i)*2; j<=n; j+=m-i){
			if(!query(j, j-m+i, br)){
//				cout << "update " << j-m+i << " " << j << endl;
				update(j, j-m+i, br);
			}
		}
		br++;
	}
/*	for(int i=1; i<=n; i++){
		cout << "parenti " << i << '\n';
		for(int j=0; j<parent[i].size(); j++){
			cout << parent[i][j].first << " " << parent[i][j].second << '\n';
		}
		cout << '\n';
	}*/
//	cout << "proso" << endl;
	int a, b;
	for(int i=0; i<q; i++){
		cin >> a >> b;
		cout << binary2(a, b) << '\n';
	}
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2944 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 3696 KB Output is correct
2 Correct 247 ms 3576 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 4060 KB Output is correct
2 Correct 223 ms 4000 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 3456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 3712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 4096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 4608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1587 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 5888 KB Time limit exceeded
2 Halted 0 ms 0 KB -