Submission #1053155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053155		tolbi	Fountain Parks (IOI21_parks)	C++17	30 / 100	703 ms	221428 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
//void build(std::vector<int> u, std::vector<int> v, std::vector<int> a, std::vector<int> b);
struct DSU{
	vector<int> par;
	int tot;
	DSU(int n):tot(n){
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	}
	bool merge(int a, int b){
		a=find(a);
		b=find(b);
		if (a!=b) tot--;
		else return false;
		par[a]=b;
		return true;
	}
};
int construct_roads(vector<int> x, vector<int> y) {
	bool subtask3 = true;
	int n = x.size();
	for (int i = 0; i < n; i++){
		if (x[i]<2 || x[i]>6) subtask3=false;
	}
	if (subtask3){
		map<pair<int,int>,int> mp;
		for (int i = 0; i < n; ++i)
		{
			mp[{x[i],y[i]}]=i;
		}
		DSU dsu(n);
		vector<int> u;
		vector<int> v;
		vector<int> xa;
		vector<int> ya;
		set<pair<int,int>> occupied;
		vector<int> lol;
		for (int i = 0; i < n; i++){
			if (mp.count({x[i],y[i]-2})){
				if (dsu.merge(i,mp[{x[i],y[i]-2}])){
					u.push_back(mp[{x[i],y[i]-2}]);
					v.push_back(i);
					ya.push_back(y[i]-1);
					if (x[i]==2) xa.push_back(x[i]-1);
					else if (x[i]==6) xa.push_back(x[i]+1);
					else {
						xa.push_back(-1);
						lol.push_back(x[i]);
					}
					if (xa.back()!=-1) occupied.insert({xa.back(),ya.back()});
				}
			}
		}
		for (int i = 0; i < n; ++i)
		{
			if (x[i]==6){
				if (mp.count({x[i]-2,y[i]})){
					if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
						u.push_back(mp[{x[i]-2,y[i]}]);
						v.push_back(i);
						xa.push_back(x[i]-1);
						ya.push_back(y[i]-1);
						occupied.insert({xa.back(),ya.back()});
					}
				}
			}
		}
		for (int i = 0; i < n; ++i)
		{
			if (x[i]!=6){
				if (mp.count({x[i]-2,y[i]})){
					if (dsu.merge(i,mp[{x[i]-2,y[i]}])){
						u.push_back(mp[{x[i]-2,y[i]}]);
						v.push_back(i);
						xa.push_back(x[i]-1);
						if (occupied.find({x[i]+1,y[i]-1})==occupied.end()){
							ya.push_back(y[i]-1);
						}
						else ya.push_back(y[i]+1);
						occupied.insert({xa.back(),ya.back()});
					}
				}
			}
		}
		reverse(lol.begin(), lol.end());
		bool boolean=true;
		for (int i = 0; i < xa.size(); i++){
			if (xa[i]==-1){
				if (occupied.find({lol.back()+1,ya[i]})==occupied.end()){
					xa[i]=lol.back()+1;
				}
				else if (occupied.find({lol.back()-1,ya[i]})==occupied.end()){
					xa[i]=lol.back()-1;
				}
				else {
					boolean=false;
					break;
				}
				lol.pop_back();
			}
		}
		if (dsu.tot==1 && boolean) {
			return build(u,v,xa,ya),1;
		}
		return 0;
	}




	//subtasks 4..5
	DSU dsu(n);
	map<pair<int,int>, int>mp;
	for (int i = 0; i < n; ++i)
	{
		mp[{x[i],y[i]}]=i;
	}
	vector<int> u;
	vector<int> v;
	vector<int> xa(n-1,-1);
	vector<int> ya(n-1,-1);
	vector<set<pair<int,int>>> arr;
	map<pair<int,int>,set<int>> qu;
	for (int i = 0; i < n; ++i)
	{
		if (mp.count({x[i]-2,y[i]})){
			if (dsu.merge(mp[{x[i]-2,y[i]}],i)){
				u.push_back(mp[{x[i]-2,y[i]}]);
				v.push_back(i);
				arr.push_back(set<pair<int,int>>());
				arr.back().insert({x[i]-1,y[i]-1});
				arr.back().insert({x[i]-1,y[i]+1});
				qu[{x[i]-1,y[i]-1}].insert(u.size()-1);
				qu[{x[i]-1,y[i]+1}].insert(u.size()-1);
			}
		}
		if (mp.count({x[i],y[i]-2})){
			if (dsu.merge(mp[{x[i],y[i]-2}],i)){
				u.push_back(mp[{x[i],y[i]-2}]);
				v.push_back(i);
				arr.push_back(set<pair<int,int>>());
				arr.back().insert({x[i]-1,y[i]-1});
				arr.back().insert({x[i]+1,y[i]-1});
				qu[{x[i]-1,y[i]-1}].insert(u.size()-1);
				qu[{x[i]+1,y[i]-1}].insert(u.size()-1);
			}
		}
	}
	if (dsu.tot!=1) return 0;
	vector<pair<int,int>> iki;
	queue<pair<int,int>> que;
	int kal = n-1;
	for (auto it : qu){
		if (it.second.size()==1) que.push(it.first);
		else iki.push_back(it.first);
	}
	while (kal>0){
		if (!que.size()){
			while (iki.size() && qu[iki.back()].size()<2) iki.pop_back();
			if (iki.size()){
				auto it = qu[iki.back()].begin();
				arr[*it].erase(iki.back());
				qu[iki.back()].erase(it);
				que.push(iki.back());
				iki.pop_back();
			}
			else return 0;
		}
		while (que.size() && qu[que.back()].size()<1) que.pop();
		pair<int,int> pr = que.front();
		que.pop();
		//bu elemani baglicam kalanina bakarik
		int it = *qu[pr].begin();
		if (xa[it]!=-1) continue;
		kal--;
		xa[it]=pr.first, ya[it]=pr.second;
		for (auto it2 : arr[it]){
			qu[it2].erase(it);
			if (qu[it2].size()==1) {
				que.push(it2);
			}
		}
		while (arr[it].size()) arr[it].erase(arr[it].begin());
	}
	build(u,v,xa,ya);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (int i = 0; i < xa.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