Submission #1213360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213360		omsincoconut	Fountain Parks (IOI21_parks)	C++17	5 / 100	622 ms	78136 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;
set<pair<int, int>> bench_used;
vector<int> ret_u, ret_v, ret_a, ret_b;

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

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

    for (int i = 0; i < 4; i++) {
        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;

        vis.insert({u, v});
        if (vis.count({v, u})) {
            dfs(v);
            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);
        }

        dfs(v);
    }
}

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;

    dfs(0);

    if (ret_u.size() < n-1) return 0;
    build(ret_u, ret_v, ret_a, ret_b);
    return 1;
}

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