Submission #1059759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059759		pcc	Fountain Parks (IOI21_parks)	C++17	70 / 100	756 ms	105676 KiB

parks

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()

const int mxn = 2e5+10;
int N;
int S;

struct DSU{
	int dsu[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		dsu[root(a)] = root(b);
	}
};

DSU dsu;

vector<int> ans[4];

void addans(int s,int e,int x,int y){
	dsu.onion(s,e);
	ans[0].push_back(s);
	ans[1].push_back(e);
	ans[2].push_back(x);
	ans[3].push_back(y);
	return;
}

map<pii,int> mp;
vector<pii> edges;
vector<pii> all;

void check(int a,int b){
	if(dsu.root(a) == dsu.root(b))return;
	edges.push_back(pii(a,b));
	dsu.onion(a,b);
	return;
}

vector<int> lef[mxn],rig[mxn*2];
int mx[mxn],my[mxn*2];
int deg[mxn*6];
bitset<mxn> done;

void dfs(int now){
	if(mx[now] != -1)return;
	int tar = -1;
	for(auto nxt:lef[now]){
		if(my[nxt] == -1){
			if(tar == -1)tar = nxt;
			else if(tar != -1&&deg[nxt]>deg[tar])tar = nxt;
		}
	}
	assert(tar != -1);
	mx[now] = tar;
	my[tar] = now;
	for(auto nxt:rig[mx[now]]){
		if(mx[nxt] == -1)dfs(nxt);
	}
	return;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	S = clock();
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
	N = x.size();
	for(int i = 0;i<N;i++){
		pii pos = pii(x[i],y[i]);
		if(mp.find(pii(pos.fs,pos.sc-2)) != mp.end())check(mp[pii(pos.fs,pos.sc-2)],i);
		if(mp.find(pii(pos.fs,pos.sc+2)) != mp.end())check(mp[pii(pos.fs,pos.sc+2)],i);
		mp[pos] = i;
	}
	for(int i = 0;i<N;i++){
		pii pos = pii(x[i],y[i]);
		if(mp.find(pii(pos.fs-2,pos.sc)) != mp.end())check(mp[pii(pos.fs-2,pos.sc)],i);
		if(mp.find(pii(pos.fs+2,pos.sc)) != mp.end())check(mp[pii(pos.fs+2,pos.sc)],i);
		mp[pos] = i;
	}
	if(edges.size() != N-1)return 0;
	for(int i = 0;i<edges.size();i++){
		auto [s,e] = edges[i];
		if(x[s]>x[e])swap(s,e);
		if(x[s] == x[e]&&y[s]>y[e])swap(s,e);
		if(x[s] == x[e]){
			all.push_back(pii(x[s]-1,(y[s]+y[e])>>1));
			all.push_back(pii(x[s]+1,(y[s]+y[e])>>1));
		}
		else if(y[s] == y[e]){
			all.push_back(pii((x[s]+x[e])>>1,y[s]-1));
			all.push_back(pii((x[s]+x[e])>>1,y[s]+1));
		}
	}
	//cerr<<"EDGES: ";for(auto [s,e]:edges)cerr<<s<<' '<<e<<endl;
	sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());
	for(int i = 0;i<edges.size();i++){
		auto [s,e] = edges[i];
		if(x[s] == x[e]){
			int p = lower_bound(_all(all),pii(x[s]-1,(y[s]+y[e])>>1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
			p = lower_bound(_all(all),pii(x[s]+1,(y[s]+y[e])>>1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
		}
		else if(y[s] == y[e]){
			int p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]-1))-all.begin();
			deg[p]++;
			rig[p].push_back(i);
			lef[i].push_back(p);
			p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]+1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
		}
	}

	queue<int> q;
	for(int i = 0;i<all.size();i++){
		if(deg[i] == 1)q.push(i);
	}

	memset(mx,-1,sizeof(mx));
	memset(my,-1,sizeof(my));

	while(!q.empty()){
		auto now = q.front();
		q.pop();
		int tar = -1;
		for(auto nxt:rig[now]){
			if(mx[nxt] == -1)tar = nxt;
		}
		if(tar == -1)continue;
		mx[tar] = now;
		my[now] = tar;
		for(auto nxt:lef[tar]){
			deg[nxt]--;
			if(deg[nxt] == 1)q.push(nxt);
		}
	}

	for(int i = 0;i<all.size();i++){
		if(my[i] != -1)continue;
		if(deg[i] == 3){
			int tar = -1;
			vector<int> v;
			map<int,int> mp;
			for(auto &j:rig[i]){
				if(mx[j] != -1)continue;
				auto &[s,e]=edges[j];
				mp[s]++;
				mp[e]++;
				if(x[s]>x[e]||(x[s] == x[e]&&y[s]>y[e]))swap(s,e);
				v.push_back(j);
			}
			pii pos = pii(-1,-1);
			for(auto &j:mp){
				if(j.sc>1){
					if(pos.fs == -1)pos.fs = j.fs;
					else pos.sc = j.fs;
				}
			}
			if(v.size() != 3)exit(0);
			assert(v.size() == 3);
			for(auto &j:v){
				auto now = edges[j];
				if(now.fs == pos.fs&&now.sc == pos.sc)tar = j;
				else if(now.fs == pos.sc&&now.sc == pos.fs)tar = j;
			}
			if(tar == -1)exit(0);
			assert(tar != -1);
			mx[tar] = i;
			my[i] = tar;
			for(auto &j:rig[i]){
				if(mx[j] == -1)dfs(j);
			}
		}
	}

	for(int i = 0;i<edges.size();i++){
		if(mx[i] != -1)continue;
		dfs(i);
	}
	

	for(int i = 0;i<edges.size();i++){
		if(mx[i] == -1)return 0;
		int tar = mx[i];
		addans(edges[i].fs,edges[i].sc,all[tar].fs,all[tar].sc);
	}

	build(ans[0],ans[1],ans[2],ans[3]);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:97: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]
   97 |  if(edges.size() != N-1)return 0;
      |     ~~~~~~~~~~~~~^~~~~~
parks.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:113:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:161:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:199:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:205:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |  for(int i = 0;i<edges.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