Submission #615643

#	Time	Username	Problem	Language	Result	Execution time	Memory
615643		HamletPetrosyan	Fountain Parks (IOI21_parks)	C++17	30 / 100	170 ms	19808 KiB

parks

#include "parks.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pii pair<pair<int, int>, int>
#define fr first.first
#define sc first.second
#define index second

const int N = 2e5 + 5;

int parent[N], sz[N];
bool point[N][2];

void make_set(int v) {
    parent[v] = v;
    sz[v] = 1;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b])
            swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}

int construct_roads(vector<int> x, vector<int> y) {
    if (len(x) == 1) {
		build({}, {}, {}, {});
        return 1;
    }

	vector<pii> vec;
	for(int i = 0; i < len(x); i++){
		vec.add({{x[i], y[i]}, i});
		make_set(i);
	}
	sort(all(vec));

	vector<int> u, v, a, b;

	int qanak = 1;
	for(int i = 1; i < len(vec); i++){
		if(vec[i].fr != vec[i - 1].fr) qanak++;
		else if(vec[i].sc - vec[i - 1].sc == 2) {
			u.add(vec[i - 1].index);
			v.add(vec[i].index);
			union_sets(vec[i - 1].index, vec[i].index);
		}
	}
	for(int i = 0; i < len(vec); i++) swap(vec[i].fr, vec[i].sc);
	sort(all(vec));

//	for(int i = 0; i < len(vec); i++){
//		cout << vec[i].fr << " " << vec[i].sc << endl;
//	}
//	cout << "---------" << endl;

	for(int i = 1; i < len(vec); i++){
		if(vec[i].fr == vec[i - 1].fr && vec[i].sc - vec[i - 1].sc == 2){
			if(find_set(vec[i].index) != find_set(vec[i - 1].index)){
				u.add(vec[i - 1].index);
				v.add(vec[i].index);
				union_sets(vec[i - 1].index, vec[i].index);
			}
		}
	}

//	for(int i = 0; i < len(u); i++){
//		cout << u[i] << " " << v[i] << endl;
//	}

	for(int i = 1; i < len(x); i++){
		if(find_set(i) != find_set(i - 1)){
			return 0;
		}
	}

	a.resize(len(u));
	b.resize(len(u));

	for(int i = 0; i < len(u); i++){
		if(x[u[i]] != x[v[i]]){
			if(x[u[i]] == 2 || x[v[i]] == 2){
				a[i] = 3;
				b[i] = y[u[i]] + 1;
				point[y[u[i]] + 1][0] = true;
			}
			continue;
		}
		if(x[u[i]] == 2){
			a[i] = x[u[i]] - 1;
			b[i] = min(y[u[i]], y[v[i]]) + 1;
		}
		if(x[u[i]] == 6){
			a[i] = x[u[i]] + 1;
			b[i] = min(y[u[i]], y[v[i]]) + 1;
		}
	}

	for(int i = 0; i < len(u); i++){
		if(x[u[i]] == x[v[i]] && x[u[i]] == 4){
			b[i] = min(y[u[i]], y[v[i]]) + 1;
			if(!point[b[i]][0]){
				a[i] = x[u[i]] - 1;
			}
			else {
				a[i] = x[u[i]] + 1;
				point[b[i]][1] = true;
			}
		}
	}

	for(int i = 0; i < len(u); i++){
		if(x[u[i]] != x[v[i]] && (x[u[i]] == 6 || x[v[i]] == 6)){
			a[i] = 5;
			b[i] = y[u[i]] + 1;
			if(point[b[i]][1]) b[i] -= 2;
		}
	}

    build(u, v, a, b);
    return 1;
}

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