Submission #1069487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069487		GusterGoose27	Fountain Parks (IOI21_parks)	C++17	45 / 100	823 ms	103612 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() || vis.find(nxt) != vis.end()) {
            continue;
        }
        ar2 epos = cur+adj[i];
        // edges.insert(epos);
        edges[epos] = {pts[cur], pts[nxt]};
        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) {
    bool comp = !is_real(sq);
    bool virt = ((edge[1]&1)&&comp);
    if (virt) sq = {-sq[0], -sq[1]};
    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+sq-edge); // must exist
    else {
        for (ar2 v1: adj) {
            if (edges.find(sq+v1) != edges.end() && matched.find(sq+v1) == matched.end()) match(sq+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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30