Submission #353996

#	Time	Username	Problem	Language	Result	Execution time	Memory
353996		algorithm16	Pictionary (COCI18_pictionary)	C++14	140 / 140	275 ms	8808 KiB

pictionary

#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 (stderr)

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 / 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