Submission #447794

#	Time	Username	Problem	Language	Result	Execution time	Memory
447794		mosiashvililuka	Fountain Parks (IOI21_parks)	C++17	0 / 100	28 ms	51924 KiB

parks

#include<bits/stdc++.h>
#include "parks.h"
#define mk make_pair
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,PI,cc,dd,cnt,CNT,bo[1000009];
pair <int, int> p[200009],P[1000009];
vector <pair <int, int> > X[200009],Y[200009];
vector <int> U,V,A,B;
map <int, int> m[200009],M[200009];
set <pair <int, pair <int, int> > > s;
set <pair <int, pair <int, int> > >::iterator it;
vector <int> v[1000009];
pair <int, int> id[1000009];
void DONE(){
	s.erase(s.lower_bound(make_pair(M[cc][dd],make_pair(cc,dd))));
	M[cc][dd]--;
	s.insert(mk(M[cc][dd],mk(cc,dd)));
}
void chk(int q, int w){
	if(m[q][w]==0) return;
	i=m[q][w];c=P[i].first;d=P[i].second;
	U.push_back(c);V.push_back(d);A.push_back(zx);B.push_back(xc);
	if(p[c].first==p[d].first){
		cc=p[c].first-1;dd=(p[c].second+p[d].second)/2;
		DONE();
		cc=p[c].first+1;dd=(p[c].second+p[d].second)/2;
		DONE();
	}else{
		cc=(p[c].first+p[d].first)/2;dd=p[c].second-1;
		DONE();
		cc=(p[c].first+p[d].first)/2;dd=p[c].second+1;
		DONE();
	}
	m[q][w]=0;
}
void DOO(){
	if(M[cc][dd]!=0){
		s.erase(s.lower_bound(make_pair(M[cc][dd],make_pair(cc,dd))));
	}
	M[cc][dd]++;
	s.insert(make_pair(M[cc][dd],make_pair(cc,dd)));
}
void CHK(int q, int w){
	if(m[q][w]==0) return;
	v[m[q][w]].push_back(cnt);
	v[cnt].push_back(m[q][w]);
}
void dfs(int q, int w){
	bo[q]=1;
	if(q<=PI){
		c=P[q].first;d=P[q].second;
		U.push_back(c);V.push_back(d);A.push_back(id[w].first);B.push_back(id[w].second);
	}
	for(vector <int>::iterator tt=v[q].begin(); tt!=v[q].end(); tt++){
		if(bo[(*tt)]==1) continue;
		dfs((*tt),q);
	}
}



int msh[200009],zm[200009];
int fnd(int q){
	if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int  q, int w){
	q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
	msh[w]=q;if(zm[q]==zm[w]) zm[q]++;
}
bool check(){
	set <int> st;
	for(i=1; i<=PI; i++){
		mrg(P[i].first,P[i].second);
	}
	for(i=1; i<=a; i++) st.insert(fnd(i));
	if(st.size()==1) return 1; else return 0;
}
int construct_roads(std::vector<int> Xx, std::vector<int> Yy) {
    a=Xx.size();
    for(i=1; i<=a; i++){
    	p[i].first=Xx[i-1];p[i].second=Yy[i-1];
	}
	for(i=1; i<=a; i++){
		X[p[i].first].push_back(make_pair(p[i].second,i));
		Y[p[i].second].push_back(make_pair(p[i].first,i));
	}
	for(i=2; i<=200000; i+=2){
		sort(X[i].begin(),X[i].end());
		sort(Y[i].begin(),Y[i].end());
		e=X[i].size();
		for(j=0; j<e-1; j++){
			if(X[i][j].first+2<X[i][j+1].first) continue;
			//cout<<i<<"  "<<X[i][j].first<<" X "<<X[i][j+1].first<<endl;
			c=X[i][j].second;d=X[i][j+1].second;
			PI++;
			P[PI].first=c;P[PI].second=d;
		}
		e=Y[i].size();
		for(j=0; j<e-1; j++){
			if(Y[i][j].first+2<Y[i][j+1].first) continue;
			//cout<<i<<"  "<<Y[i][j].first<<" Y "<<Y[i][j+1].first<<endl;
			c=Y[i][j].second;d=Y[i][j+1].second;
			PI++;
			P[PI].first=c;P[PI].second=d;
		}
	}
	if(check()==0){
		return 0;
	}
	/*cout<<PI<<endl;
	for(i=1; i<=PI; i++){
		c=P[i].first;d=P[i].second;
		cout<<p[c].first<<" "<<p[c].second<<"   "<<p[d].first<<" "<<p[d].second<<endl;
	}
	exit(0);*/
	for(i=1; i<=PI; i++){
		c=P[i].first;d=P[i].second;
		m[(p[c].first+p[d].first)/2][(p[c].second+p[d].second)/2]=i;
		if(p[c].first==p[d].first){
			cc=p[c].first-1;dd=(p[c].second+p[d].second)/2;
			DOO();
			cc=p[c].first+1;dd=(p[c].second+p[d].second)/2;
			DOO();
		}else{
			cc=(p[c].first+p[d].first)/2;dd=p[c].second-1;
			DOO();
			cc=(p[c].first+p[d].first)/2;dd=p[c].second+1;
			DOO();
		}
	}
	while(s.size()){
		it=s.begin();
		if((*it).first>=2) break;
		if((*it).first==0){
			s.erase(it);continue;
		}
		int ca=(*it).second.first,da=(*it).second.second;
		zx=ca;xc=da;
		chk(ca-1,da);chk(ca+1,da);chk(ca,da-1);chk(ca,da+1);
	}
	/*cout<<U.size()<<endl;
	for(i=0; i<U.size(); i++){
		cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
	}
	exit(0);*/
	cnt=PI+1;
	for(it=s.begin(); it!=s.end(); it++){
		cnt++;id[cnt]=(*it).second;
		CHK((*it).second.first-1,(*it).second.second);
		CHK((*it).second.first+1,(*it).second.second);
		CHK((*it).second.first,(*it).second.second-1);
		CHK((*it).second.first,(*it).second.second+1);
	}
	for(i=PI+1; i<=cnt; i++){
		if(bo[i]!=0) continue;
		dfs(i,0);
	}
	build(U,V,A,B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'void mrg(int, int)':
parks.cpp:67:44: warning: self-comparison always evaluates to false [-Wtautological-compare]
   67 |  q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
      |                                       ~~~~~^~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30