Submission #435914

#	Time	Username	Problem	Language	Result	Execution time	Memory
435914		rqi	Fountain Parks (IOI21_parks)	C++17	100 / 100	1169 ms	63596 KiB

parks

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

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define ins insert
#define bk back()
#define lb lower_bound

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

const int MOD = 1e9+7;

struct DSUreg{
	vi e;
	void init(int n){
		e = vi(n+1, -1);
	}

	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}

	bool unite(int a, int b){
		a = get(a); b = get(b);
		if(a == b) return 0;

		if(-e[a] < -e[b]) swap(a, b);

		e[a]+=e[b];
		e[b] = a;

		return 1;
	}
};

int n;

const int mx = 200005;
set<pi> at_x[mx];
DSUreg dsu;

int getPoint(pi a){
	auto it = at_x[a.f].lb(mp(a.s, 0));
	if(it != at_x[a.f].end() && it->f == a.s){
		return it->s;
	}
	return -1;
}

vpi best_dirs[2] = {vpi{mp(-1, 0), mp(1, 0), mp(0, 1), mp(0, -1)}, vpi{mp(0, 1), mp(0, -1), mp(-1, 0), mp(1, 0)}};

int construct_roads(vi x, vi y) {
	n = sz(x);
	dsu.init(n+5);
   	if(n == 1){
   		build({}, {}, {}, {});
   		return 1;
   	}

    vi u, v, a, b;

    set<pi> benches;
    for(int i = 0; i < n; i++){
        for(int x_ch = -1; x_ch <= 1; x_ch+=2){
            for(int y_ch = -1; y_ch <= 1; y_ch+=2){
                benches.ins(mp(x[i]+x_ch, y[i]+y_ch));
            }
        }
    }

    map<pi, int> fountains;
    for(int i = 0; i < n; i++){
        fountains[mp(x[i], y[i])] = i;
    }

    for(auto bench: benches){
        // cout << "bench: " << bench.f << " " << bench.s << "\n";
        int parity = (bench.f/2+bench.s/2) % 2;
        for(auto dir: best_dirs[parity]){
            pi pos1 = mp(bench.f+dir.f-dir.s, bench.s+dir.s+dir.f);
            pi pos2 = mp(bench.f+dir.f+dir.s, bench.s+dir.s-dir.f);
            if(fountains.count(pos1) && fountains.count(pos2)){
                int ind1 = fountains[pos1];
                int ind2 = fountains[pos2];
                
                if(dsu.unite(ind1, ind2)){
                    u.pb(ind1);
                    v.pb(ind2);
                    a.pb(bench.f);
                    b.pb(bench.s);

                    // cout << ind1 << " " << ind2 << "\n";
                }
                
                break;
            }
        }
    }

    for(int i = 0; i < n; i++){
    	if(dsu.get(i) != dsu.get(0)){
    		return 0;
    	}
    }

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

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