Submission #1213364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213364		omsincoconut	Fountain Parks (IOI21_parks)	C++17	50 / 100	1629 ms	180972 KiB

parks

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

using namespace std;

vector<int> x, y;
map<pair<int, int>, int> pos_idx;
map<pair<int, int>, int> edge_side;
set<pair<int, int>> vis, benched;
set<pair<int, int>> bench_used;
vector<int> ret_u, ret_v, ret_a, ret_b;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void dfs(int u, int ent) {
    int xu = x[u], yu = y[u];

    for (int id = 0; id < 4; id++) {
        int i = (ent+id+1)%4;
        int xv = x[u] + 2*dx[i], yv = y[u] + 2*dy[i];
        if (!pos_idx.count({xv, yv})) continue;
        int v = pos_idx[{xv, yv}];

        if (vis.count({u, v})) continue;

        if (benched.count({v, u})) {
            vis.insert({u, v});
            dfs(v, i);
            continue;
        }

        int bx, by;

        if (dx[i] == 1) {
            bx = xu + dx[i];
            by = yu + 1;
        } else if (dx[i] == -1) {
            bx = xu + dx[i];
            by = yu - 1;
        } else if (dy[i] == 1) {
            bx = xu - 1;
            by = yu + dy[i];
        } else if (dy[i] == -1) {
            bx = xu + 1;
            by = yu + dy[i];
        }

        if (!bench_used.count({bx, by})) {
            ret_u.push_back(u);
            ret_v.push_back(v);
            ret_a.push_back(bx);
            ret_b.push_back(by);
            bench_used.insert({bx, by});
            benched.insert({u, v});
        }

        vis.insert({u, v});
        dfs(v, i);
    }
}

int construct_roads(vector<int> _x, vector<int> _y) {
    x = _x; y = _y;
    int n = x.size();
    for (int i = 0; i < n; i++) pos_idx[{x[i], y[i]}] = i;

    int start = 0;
    for (int i = 0; i < n; i++) {
        if (make_pair(y[i], -x[i]) > make_pair(y[start], -x[start])) start = i;
    }

    dfs(start, 0);

    // Check connectivity
    vector<vector<int>> edge_used(n, vector<int>());
    for (int i = 0; i < ret_u.size(); i++) {
        edge_used[ret_u[i]].push_back(ret_v[i]);
        edge_used[ret_v[i]].push_back(ret_u[i]);
    }

    vector<bool> visited(n);
    queue<int> bfs;
    bfs.push(0);
    while (!bfs.empty()) {
        int u = bfs.front();
        bfs.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (int v : edge_used[u]) bfs.push(v);
    }

    for (int i = 0; i < n; i++) if (!visited[i]) return 0;

    build(ret_u, ret_v, ret_a, ret_b);
    return 1;
}

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