oj.uz

Submission #353996

# Submission time Handle Problem Language Result Execution time Memory
353996 2021-01-21T11:34:00 Z algorithm16 Pictionary (COCI18_pictionary) C++14
140 / 140
 275 ms 8808 KB 
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,q,sol[100005],parent[100005],dep[100005];
vector <pair<int,int> > v,v1;
vector <int> ind;
int find_par(int x) {
	if(x==parent[x]) return x;
	int par=find_par(parent[x]);
	if(parent[x]!=par) v1.push_back(make_pair(x,parent[x]));
	parent[x]=par;
	return par;
}
void s(int x,int y) {
	x=find_par(x);
	y=find_par(y);
	if(x==y) return;
	if(dep[x]==dep[y]) dep[x]+=1;
	if(dep[x]>dep[y]) {
		v1.push_back(make_pair(y,parent[y]));
		parent[y]=x;
	}
	else {
		v1.push_back(make_pair(x,parent[x]));
		parent[x]=y;
	}
}
void rek(int lo,int hi) {
	if(ind.empty()) return;
	//cout << lo << " " << hi << " " << ind.size() << "\n";
	if(lo==hi) {
		for(int i=0;i<ind.size();i++) {
			sol[ind[i]]=lo;
		}
		return;
	}
	int mid=(lo+hi)/2;
	int s1=v1.size();
	for(int i=lo;i<=mid;i++) {
		int x=m-i,ind=m-i-1;
		for(int j=2*x-1;j<n;j+=x) {
			s(ind,j);
			ind=j;
		}
	}
	vector <int> l,r;
	for(int i=0;i<ind.size();i++) {
		if(find_par(v[ind[i]].first)==find_par(v[ind[i]].second)) l.push_back(ind[i]);
		else r.push_back(ind[i]);
	}
	ind=r;
	rek(mid+1,hi);
	while(v1.size()>s1) {
		pair <int,int> p=v1.back();
		parent[p.first]=p.second;
		v1.pop_back();
	}
	ind=l;
	rek(lo,mid);
}
int main()
{
	cin >> n >> m >> q;
	for(int i=0;i<n;i++) {
		parent[i]=i;
	}
	for(int i=0;i<q;i++) {
		int a,b;
		cin >> a >> b;
		v.push_back(make_pair(a-1,b-1));
		ind.push_back(i);
	}
	//cout << 2405/65 << "\n";
	rek(0,m-1);
	for(int i=0;i<q;i++) {
		cout << sol[i]+1 << "\n";
	}
	return 0;
}

Compilation message

pictionary.cpp: In function 'void rek(int, int)':
pictionary.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<ind.size();i++) {
      |               ~^~~~~~~~~~~
pictionary.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<ind.size();i++) {
      |              ~^~~~~~~~~~~
pictionary.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |  while(v1.size()>s1) {
      |        ~~~~~~~~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1256 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4064 KB Output is correct
2 Correct 57 ms 3572 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5472 KB Output is correct
2 Correct 78 ms 4704 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3556 KB Output is correct
2 Correct 76 ms 3300 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3940 KB Output is correct
2 Correct 90 ms 3300 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 5472 KB Output is correct
2 Correct 120 ms 3808 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 4980 KB Output is correct
2 Correct 195 ms 7004 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 7956 KB Output is correct
2 Correct 231 ms 6908 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 8808 KB Output is correct
2 Correct 263 ms 7772 KB Output is correct