Submission #827021

#	Time	Username	Problem	Language	Result	Execution time	Memory
827021		NothingXD	Fountain Parks (IOI21_parks)	C++17	70 / 100	564 ms	98312 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, x[maxn], y[maxn], dsu[maxn], cntedge[maxn], cntdot[maxn<<1], a[maxn], b[maxn];
vector<int> numx[maxn], numy[maxn];
vector<pair<pii,int>> p;
vector<pii> edge;
vector<pii> dot;
vector<int> gedge[maxn], gdot[maxn<<1];
bool markedge[maxn];
bool markdot[maxn<<1];
set<pii> st;
int getdsu(int v){
	return (dsu[v] < 0? v: dsu[v] = getdsu(dsu[v]));
}

bool merge(int u, int v){
	if ((u = getdsu(u)) == (v = getdsu(v))) return false;
	dsu[u] = v;
	return true;
}

pair<pii,pii> getdot(int u, int v){
	//debug(x[u], x[v], y[u], y[v]);
	if (x[u] == x[v]) return {{x[u]-1, (y[u]+y[v])/2}, {x[u]+1, (y[u]+y[v])/2}};
	return {{(x[u]+x[v])/2, y[u]-1}, {(x[u]+x[v])/2, y[u]+1}};
}

void rmdot(int idx){
	for (auto x: gdot[idx]){
		if (!markedge[x]){
			st.erase({cntedge[x], x});
			cntedge[x]--;
			st.insert({cntedge[x], x});
		}
	}
}

void rmedge(int idx){
	for (auto x: gedge[idx]){
		if (!markdot[x]){
			st.erase({cntdot[x], x+n});
			cntdot[x]--;
			st.insert({cntdot[x], x+n});
		}
	}
}


int construct_roads(std::vector<int> X, std::vector<int> Y) {
	memset(dsu, -1, sizeof dsu);
	n = X.size();
	for (int i = 0; i < n; i++){
		x[i] = X[i];
		y[i] = Y[i];
		p.push_back({{X[i], Y[i]}, i});
		numx[X[i]].push_back(Y[i]);
		numy[Y[i]].push_back(X[i]);
	}
	sort(all(p));
	for (int i = 0; i < maxn; i++){
		sort(all(numx[i]));
		for (int j = 1; j < numx[i].size(); j++){
			if (numx[i][j-1] + 2 == numx[i][j]){
				int u = (*lower_bound(all(p), MP(MP(i, numx[i][j-1]), 0))).S;
				int v = (*lower_bound(all(p), MP(MP(i, numx[i][j]), 0))).S;
				if (merge(u, v)) edge.push_back({u, v});
			}
		}
		sort(all(numy[i]));
		for (int j = 1; j < numy[i].size(); j++){
			if (numy[i][j-1] + 2 == numy[i][j]){
				int u = (*lower_bound(all(p), MP(MP(numy[i][j-1], i), 0))).S;
				int v = (*lower_bound(all(p), MP(MP(numy[i][j], i), 0))).S;
				if (merge(u, v)) edge.push_back({u, v});
			}
		}
	}
	if (edge.size() != n-1) return 0;
	for (int i = 0; i < n-1; i++){
		pair<pii,pii> tmp = getdot(edge[i].F, edge[i].S);
//		debug(edge[i].F, edge[i].S, tmp.F.F, tmp.F.S, tmp.S.F, tmp.S.S);
		dot.push_back(tmp.F);
		dot.push_back(tmp.S);
	}
	sort(all(dot));
	dot.resize(distance(dot.begin(), unique(all(dot))));
	for (int i = 0; i < n-1; i++){
		cntedge[i] = 2;
		pair<pii,pii> tmp = getdot(edge[i].F, edge[i].S);
		int idx = lower_bound(all(dot), tmp.F) - dot.begin();
	//	debug(i, idx);
		gdot[idx].push_back(i);
		gedge[i].push_back(idx);
		cntdot[idx]++;
		idx = lower_bound(all(dot), tmp.S) - dot.begin();
	//	debug(i, idx);
		gdot[idx].push_back(i);
		gedge[i].push_back(idx);
		cntdot[idx]++;
	}
	for (int i = 0; i < n-1; i++){
	//	debug(i, edge[i].F, edge[i].S, cntedge[i]);
		st.insert({cntedge[i], i});
	}
	for (int i = 0; i < dot.size(); i++){
		//debug(i, dot[i].F, dot[i].S, cntdot[i]);
		st.insert({cntdot[i], n+i});
	}
	while(!st.empty()){
		pii v = *st.begin();
		st.erase(st.begin());
		//debug(v.F, v.S);
		if (v.F == 0){
			assert(v.S >= n);
			continue;
		}
		if (v.S > n){
			v.S -= n;
			markdot[v.S] = true;
			for (auto x: gdot[v.S]){
//				debug(x);
				if (!markedge[x]){
//					debug(x, v.S);
					markedge[x] = true;
					a[x] = dot[v.S].F;
					b[x] = dot[v.S].S;
					st.erase({cntedge[x], x});
					rmdot(v.S);
					rmedge(x);
					break;
				}
			}
		}
		else{
			markedge[v.S] = true;
			for (auto x: gedge[v.S]){
				if (!markdot[x]){
//					debug(v.S, x);
					markdot[x] = true;
					a[v.S] = dot[x].F;
					b[v.S] = dot[x].S;
					st.erase({cntdot[x], x+n});
					rmdot(x);
					rmedge(v.S);
					break;
				}
			}
		}
	}
	vector<int> U, V, A, B;
	for (int i = 0; i < n-1; i++){
		U.push_back(edge[i].F);
		V.push_back(edge[i].S);
		A.push_back(a[i]);
		B.push_back(b[i]);
	}
	build(U, V, A, B);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int j = 1; j < numx[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
parks.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for (int j = 1; j < numy[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~
parks.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |  if (edge.size() != n-1) return 0;
      |      ~~~~~~~~~~~~^~~~~~
parks.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for (int i = 0; i < dot.size(); i++){
      |                  ~~^~~~~~~~~~~~

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