제출 #435420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435420		mraron	분수 공원 (IOI21_parks)	C++17	5 / 100	930 ms	58924 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;

struct dsu {
	vector<int> par;
	vector<int> sz;
	dsu(int n) : par(n,-1) {sz.assign(n,1);}
	
	int get(int x) {
		if(par[x]==-1) return x;
		return par[x]=get(par[x]);
	}
	
	void merge(int x, int y) {
		int px=get(x), py=get(y);
		if(px==py) return ;
		
		if(sz[px]>sz[py]) {
			swap(px,py);
			swap(x,y); //:) lyft
		}
		
		sz[py]+=sz[px];
		par[px]=py;
	}
};

int d0[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

pair<int,int> kp(pair<int,int> a, pair<int,int> b) {
	return {(a.first+b.first)/2, (a.second+b.second)/2};
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
		build({}, {}, {}, {});
		return 1;
    }
    
    int n=x.size();
    vector<pair<pair<int,int>, int>> ord;
    vector<pair<int,int>> lst;
    for(int i=0;i<n;++i) {
		ord.push_back({{x[i], y[i]}, i});
		lst.push_back({x[i], y[i]});
	}
    
    sort(ord.begin(), ord.end());
    
    auto ker=[&](pair<int,int> coords) -> int {
		auto it=lower_bound(ord.begin(), ord.end(), make_pair(coords, 0));
		if(it==ord.end() || it->first!=coords) return -1;
		return it->second;
	};
    
    dsu d(n);
    vector<pair<int,int>> edgs;
    for(int i=0;i<n;++i) {
		for(int j=0;j<4;++j) {
			int nx=x[i]+d0[j][0]*2, ny=y[i]+d0[j][1]*2;
			int ind=ker(make_pair(nx,ny));
			if(ind!=-1) {
				if(d.get(i)!=d.get(ind)) {
					d.merge(i, ind);
					edgs.push_back({i, ind});
				}
			}
		}
	}
	
	if(d.sz[d.get(0)]!=n) {
		return 0;
	} 
	
	map<pair<int,int>, int> cnt;
	set<pair<int, pair<int,int>>> st;
	map<pair<int,int>, int> in_st;
	for(int i=0;i<(int)edgs.size();++i) {
		st.insert({0, edgs[i]});
		in_st[edgs[i]]=1;
	}

	map<pair<int,int>, pair<int,int>> kozpont;
	for(int i=0;i<(int)edgs.size();++i) {
		kozpont[kp(lst[edgs[i].first], lst[edgs[i].second])]=edgs[i];
	}

	map<pair<int,int>, pair<int,int>> rel;
	
	set<pair<int,int>> benches_set;
	
	while(!st.empty()) {
		auto akt=*st.begin();st.erase(st.begin());
		in_st[akt.second]=0;
		if(akt.first==-2) assert(0);
		pair<int,int> first_point=lst[akt.second.first];
		pair<int,int> second_point=lst[akt.second.second];
		
		pair<int,int> alt1=kp(first_point, second_point);
		pair<int,int> alt2=alt1;
		if(first_point.first!=second_point.first) {
			alt1.second--;
			alt2.second++;
		}else {
			alt1.first--;
			alt2.first++;
		}
		
		pair<int,int> bench;
		if(benches_set.find(alt1)==benches_set.end()) {
			bench=alt1;
		}else if(benches_set.find(alt2)==benches_set.end()) {
			bench=alt2;
		}else {
			assert(0); //?
		}
		
		rel[akt.second]=bench;
		for(int i=0;i<4;++i) {
			int nx=bench.first+d0[i][0], ny=bench.second+d0[i][1];
			pair<int,int> ind={nx,ny};
			if(kozpont.count(ind) && in_st[kozpont[ind]]) {
				st.erase({cnt[kozpont[ind]]--, kozpont[ind]});
				st.insert({cnt[kozpont[ind]], kozpont[ind]});
			}
		}
	}
	
	vector<pair<int,int>> benches(edgs.size());
	for(int i=0;i<(int)edgs.size();++i) {
		benches[i]=rel[edgs[i]];
	}
    
    vector<int> A(edgs.size()),B(edgs.size()),C(edgs.size()),D(edgs.size());
    for(int i=0;i<(int)edgs.size();++i) A[i]=edgs[i].first;
    for(int i=0;i<(int)edgs.size();++i) B[i]=edgs[i].second;
    for(int i=0;i<(int)edgs.size();++i) C[i]=benches[i].first;
    for(int i=0;i<(int)edgs.size();++i) D[i]=benches[i].second;
    
    build(A,B,C,D);
    
    return 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