Submission #614107

#	Time	Username	Problem	Language	Result	Execution time	Memory
614107		dxz05	Fountain Parks (IOI21_parks)	C++17	100 / 100	811 ms	56696 KiB

parks

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

using namespace std;
#define MP make_pair
#define all(x) (x).begin(), (x).end()

struct dsu {
    vector<int> p, sz;
    dsu(int n) {
        p.assign(n, 0);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        return (x == p[x] ? x : p[x] = find(p[x]));
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
};

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

    map<pair<int, int>, int> id;
    set<pair<int, int>> benches;
    for (int i = 0; i < n; i++){
        id[MP(x[i], y[i])] = i;
        benches.insert(MP(x[i] - 1, y[i] - 1));
        benches.insert(MP(x[i] - 1, y[i] + 1));
        benches.insert(MP(x[i] + 1, y[i] - 1));
        benches.insert(MP(x[i] + 1, y[i] + 1));
    }

    vector<int> U, V, A, B;
    dsu d(n);
    
    for (pair<int, int> bench : benches){
        int a = bench.first, b = bench.second;
        
        int par = ((a - 1) / 2 + (b - 1) / 2) % 2;

        // cerr << a << ' ' << b << ' ' << par << endl;

        if (par){ // down, up
            int i = -1, j = -1;
            if (id.find(MP(a - 1, b - 1)) != id.end()) i = id[MP(a - 1, b - 1)];
            if (id.find(MP(a + 1, b - 1)) != id.end()) j = id[MP(a + 1, b - 1)];
            if (i != -1 && j != -1 && d.unite(i, j)){
                U.push_back(i);
                V.push_back(j);
                A.push_back(a);
                B.push_back(b);
                continue;                
            }

            i = -1, j = -1;
            if (id.find(MP(a - 1, b + 1)) != id.end()) i = id[MP(a - 1, b + 1)];
            if (id.find(MP(a + 1, b + 1)) != id.end()) j = id[MP(a + 1, b + 1)];
            if (i != -1 && j != -1 && d.unite(i, j)) {
                U.push_back(i);
                V.push_back(j);
                A.push_back(a);
                B.push_back(b);
                continue;
            }

        } else { // left, right
            int i = -1, j = -1;
            if (id.find(MP(a - 1, b - 1)) != id.end()) i = id[MP(a - 1, b - 1)];
            if (id.find(MP(a - 1, b + 1)) != id.end()) j = id[MP(a - 1, b + 1)];
            if (i != -1 && j != -1 && d.unite(i, j)) {
                U.push_back(i);
                V.push_back(j);
                A.push_back(a);
                B.push_back(b);
                continue;
            }

            i = -1, j = -1;
            if (id.find(MP(a + 1, b - 1)) != id.end()) i = id[MP(a + 1, b - 1)];
            if (id.find(MP(a + 1, b + 1)) != id.end()) j = id[MP(a + 1, b + 1)];
            if (i != -1 && j != -1 && d.unite(i, j)) {
                U.push_back(i);
                V.push_back(j);
                A.push_back(a);
                B.push_back(b);
                continue;
            }
        }

    }

    if ((int)U.size() == n - 1){
        build(U, V, A, B);
        return 1;
    }
    
    return 0;
}

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