Submission #1069488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069488		GusterGoose27	Fountain Parks (IOI21_parks)	C++17	100 / 100	1335 ms	121416 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>

using namespace std;

#define sz(s) ((int)s.size())

typedef array<int, 2> ar2;
// set<ar2> pts;
map<ar2, ar2> edges;
map<ar2, int> pts;
// set<ar2> edges;
set<ar2> vis;
int n;
vector<int> u, v, a, b;
set<ar2> matched;

vector<ar2> adj2({{2, 0}, {0, 2}, {-2, 0}, {0, -2}});
vector<ar2> adj({{1, 0}, {0, 1}, {-1, 0}, {0, -1}});

ar2 operator+(ar2 a, ar2 b) {
    return {a[0]+b[0], a[1]+b[1]};
}

ar2 operator-(ar2 a, ar2 b) {
    return {a[0]-b[0], a[1]-b[1]};
}

void dfs(ar2 cur) {
    vis.insert(cur);
    for (int i = 0; i < 4; i++) {
        ar2 nxt = cur+adj2[i];
        if (pts.find(nxt) == pts.end()) {
            continue;
        }
        ar2 epos = cur+adj[i];
        edges[epos] = {pts[cur], pts[nxt]};
        if (vis.find(nxt) == vis.end()) dfs(nxt);
    }
}

bool is_real(ar2 &square) {
    int s = 0;
    for (ar2 v1: adj) s += (edges.find(square+v1) != edges.end());
    return s <= 2;
}

void match(ar2 e);

bool match(ar2 edge, ar2 sq_orig) {
    bool comp = !is_real(sq_orig);
    bool virt = ((edge[1]&1)&&comp);
    ar2 sq = (virt ? ar2({-sq_orig[0], -sq_orig[1]}) : sq_orig);
    if (matched.find(sq) != matched.end()) return 0;
    if (!virt) {
        u.push_back(edges[edge][0]);
        v.push_back(edges[edge][1]);
        a.push_back(sq[0]);
        b.push_back(sq[1]);
    }
    matched.insert(sq);
    matched.insert(edge);
    if (comp) match(sq_orig+sq_orig-edge); // must exist
    else {
        for (ar2 v1: adj) {
            if (edges.find(sq_orig+v1) != edges.end() && matched.find(sq_orig+v1) == matched.end()) match(sq_orig+v1);
        }
    }
    return 1;
}

void match(ar2 edge) {
    if (matched.find(edge) != matched.end()) return;
    if (edge[0]&1) { // horizontal edge
        if (!match(edge, edge+ar2({0,1}))) assert(match(edge, edge+ar2({0, -1})));
    }
    else if (!match(edge, edge+ar2({1, 0}))) assert(match(edge, edge+ar2({-1, 0})));
}

int construct_roads(vector<int> x, vector<int> y) {
    n = sz(x);
    for (int i = 0; i < n; i++) {
        // pts.insert({x[i], y[i]});
        pts[{x[i], y[i]}] = i;
    }
    dfs({x[0], y[0]});
    if (sz(vis) != n) return 0;
    for (auto v: edges) match(v.first);
    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