Submission #436725

#	Time	Username	Problem	Language	Result	Execution time	Memory
436725		Apiram	Fountain Parks (IOI21_parks)	C++17	5 / 100	3544 ms	18784 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>parent(2e5);
vector<int>siz(2e5);
int maxxy=0;
void makesets(int v){
	parent[v]=v;
	siz[v]=1;
}
int findsets (int v){
	if (v==parent[v])return v;
	parent[v]=findsets(parent[v]);
	return parent[v];
}
void unionset(int a,int b){
	a = findsets(a);
	b =findsets(b);
	if (a==b)return;
	if (siz[a]<siz[b])swap(a,b);
	siz[a]+=siz[b];
	maxxy=max(siz[a],maxxy);
	parent[b]=a;
}
struct point {
	int x,y,index;
};
bool dist(point x,point y){
	if (pow(x.x - y.x,2)+pow(x.y-y.y,2)!=4)return false;
	return true;
}
int binarysearch(int seg,int eq,int n,vector<point>arr){
	int left = 0;
	int right = n-1;
	while(left<=right){
		int mid = (left + right) >> 1;
		if (arr[mid].x<seg)left= mid + 1;
		else if (arr[mid].x>seg)right = mid-1;
		else {
			if (arr[mid].y<eq){
				left=mid+1;
			}
			else if (arr[mid].y>eq){
				right = mid-1;
			}
			else return mid;
		}
	}
	if (left>=0&&left<n)return left;
	return 0;
}
//void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) ;
int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<point>arr;
    int n = x.size();
    bool ok=true;
    
    for (int i = 0 ;i<n;++i){
    	if (x[i]!=x[0])ok=false;
    	arr.push_back({x[i],y[i],i});
    }
    vector<int>ansx,ansy,ansxi,ansyi;
    if (ok){
    sort(arr.begin(),arr.end(),[&](point a,point b){
    	return a.y<b.y;
    });
    
    for (int i = 1;i<n;++i){
    	if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y)+1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    	}
    	else return 0;
    }
    build(ansxi,ansyi,ansx,ansy);
    return 1;}
    else{
    	for (int i =0;i<n;++i){
    		makesets(i);
    	}
    	vector<vector<bool>>p(3,vector<bool>(1e5 + 5,false));
    	sort(arr.begin(),arr.end(),[&](point a,point b){
    		if (a.x==b.x)return a.y<b.y;
    		return a.x<b.x;
    });
    vector<int>check;
    	int i =1;
    	for (;i<n;++i){
    		if (arr[i].x!=2)break;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) - 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		unionset(i-1,i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    		else {
    			check.push_back(i);
    			check.push_back(i-1);
    		}
    	}
    		check.push_back(i);
    		check.push_back(i-1);
    
    	for (;i<n;++i){
    		if (arr[i-1].x==2)continue;
    		if (dist(arr[i],arr[i-1])){
    		ansx.push_back(min(arr[i].x,arr[i-1].x) + 1);
    		ansy.push_back(min(arr[i].y,arr[i-1].y) + 1);
    		ansxi.push_back(arr[i].index);
    		ansyi.push_back(arr[i-1].index);
    		unionset(i-1,i);
    		p[ansx.back()/2][ansy.back()/2]=true;
    		}
    		else {
    			check.push_back(i-1);
    		}
    	}
    
    	
    for (int l = 0;l<check.size();++l){
    	int k = check[l];
    	if (maxxy==n)break;
    	int ls=(arr[k].x==2)?binarysearch(arr[k].x+2,arr[k].y,n,arr):-1;
    	int lt =(arr[k].x==4)?binarysearch(arr[k].x-2,arr[k].y,n,arr):-1;
    	vector<int>crr;
    	if (ls!=-1)crr.push_back(ls);
    	if (lt!=-1)crr.push_back(lt);
    	for (auto j:crr){
    		if (dist(arr[j],arr[k])&&findsets(j)!=findsets(k)){
    		int first1=min(arr[k].x,arr[j].x) + 1;
    		int first2=min(arr[k].x,arr[j].x) + 1;
    		int second1=min(arr[k].y,arr[j].y) + 1;
    		int second2 = min(arr[k].y,arr[j].y) - 1;
    		if (!p[first1/2][second1/2]){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second1);
    			ansxi.push_back(arr[j].index);
    			ansyi.push_back(arr[k].index);
    			unionset(j,k);
    			p[ansx.back()/2][ansy.back()/2]=true;
    			break;
    		}
    		if (!p[first1/2][second1/2]){
    			ok=true;
    			ansx.push_back(first1);
    			ansy.push_back(second2);
    			ansxi.push_back(arr[j].index);
    			ansyi.push_back(arr[k].index);
    			unionset(j,k);
    			p[ansx.back()/2][ansy.back()/2]=true;
    			break;
    		}
    		
    		}
    	}
    	
    }
    if (maxxy!=n)return 0;
    	  build(ansxi,ansyi,ansx,ansy);
    	  return 1;
    }
    
    
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int l = 0;l<check.size();++l){
      |                    ~^~~~~~~~~~~~~
parks.cpp:135:11: warning: unused variable 'first2' [-Wunused-variable]
  135 |       int first2=min(arr[k].x,arr[j].x) + 1;
      |           ^~~~~~

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