Submission #447822

#	Time	Username	Problem	Language	Result	Execution time	Memory
447822		mosiashvililuka	Fountain Parks (IOI21_parks)	C++17	30 / 100	188 ms	35376 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;
pair <int, int> p[200009],P[1000009];
vector <pair <int, int> > X[200009],Y[200009];
vector <int> U,V,A,B;
bool bo[9][200009];
int fx[9][200009];
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];
    	fx[p[i].first][p[i].second]=i;
	}
	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<=6; i+=2){
		sort(X[i].begin(),X[i].end());
		if(i==4) continue;
		e=X[i].size();
		for(j=0; j<e-1; j++){
			if(X[i][j].first+2<X[i][j+1].first) continue;
			c=X[i][j].second;d=X[i][j+1].second;
			U.push_back(c);V.push_back(d);
			if(i==2){
				A.push_back(i-1);B.push_back((p[c].second+p[d].second)/2);
			}else{
				A.push_back(i+1);B.push_back((p[c].second+p[d].second)/2);
			}
		}
	}
	i=4;e=X[i].size();cc=0;
	for(j=0; j<e-1; j++){
		if(X[i][j].first+2<X[i][j+1].first){
			cc=0;
			continue;
		}
		c=X[i][j].second;d=X[i][j+1].second;
		U.push_back(c);V.push_back(d);
		if(cc==0){
			A.push_back(i+1);B.push_back((p[c].second+p[d].second)/2);
		}else{
			A.push_back(i-1);B.push_back((p[c].second+p[d].second)/2);
		}
		cc^=1;
	}
	for(i=0; i<A.size(); i++){
		bo[A[i]][B[i]]=1;
	}
	for(j=2; j<=200000; j++){
		if(fx[2][j]==0||fx[4][j]==0) continue;
		if(bo[3][j-1]==0){
			bo[3][j-1]=1;
			U.push_back(fx[2][j]);V.push_back(fx[4][j]);
			A.push_back(3);B.push_back(j-1);
			continue;
		}
		if(bo[3][j+1]==0){
			bo[3][j+1]=1;
			U.push_back(fx[2][j]);V.push_back(fx[4][j]);
			A.push_back(3);B.push_back(j+1);
			continue;
		}
	}
	for(j=2; j<=200000; j++){
		if(fx[4][j]==0||fx[6][j]==0) continue;
		if(bo[5][j-1]==0){
			bo[5][j-1]=1;
			U.push_back(fx[4][j]);V.push_back(fx[6][j]);
			A.push_back(5);B.push_back(j-1);
			continue;
		}
		if(bo[5][j+1]==0){
			bo[5][j+1]=1;
			U.push_back(fx[4][j]);V.push_back(fx[6][j]);
			A.push_back(5);B.push_back(j+1);
			continue;
		}
	}
	/*cout<<U.size()<<endl;
	for(i=0; i<U.size(); i++){
		cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
	}*/
	for(i=0; i<U.size(); i++){
		PI++;P[PI].first=U[i];P[PI].second=V[i];
	}
	if(check()==0){
		return 0;
	}
	
	for(i=0; i<U.size(); i++){
		U[i]--;V[i]--;
	}
	build(U,V,A,B);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'void mrg(int, int)':
parks.cpp:16:44: warning: self-comparison always evaluates to false [-Wtautological-compare]
   16 |  q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
      |                                       ~~~~~^~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(i=0; i<A.size(); i++){
      |           ~^~~~~~~~~
parks.cpp:104:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for(i=0; i<U.size(); i++){
      |           ~^~~~~~~~~
parks.cpp:111:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(i=0; i<U.size(); i++){
      |           ~^~~~~~~~~

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