Submission #1029767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029767		aufan	Fountain Parks (IOI21_parks)	C++17	100 / 100	668 ms	72380 KiB

parks

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

using namespace std;

const int fx[] = {1, 1, -1, -1};
const int fy[] = {1, -1, 1, -1};
const int dx[] = {2, 0, -2, 0};
const int dy[] = {0, 2, 0, -2};

int construct_roads(vector<int> x, vector<int> y) {
    int n = (int)x.size();
    map<pair<int, int>, int> id;
    set<pair<int, int>> pos;
    for (int i = 0; i < n; i++) {
        id[{x[i], y[i]}] = i;
        
        for (int k = 0; k < 4; k++) {
            int nx = x[i] + fx[k];
            int ny = y[i] + fy[k];
            pos.insert({nx, ny});
        }
    }

    vector<int> vis(n);

    function<void(int)> dfs = [&](int z) {
        vis[z] = 1;

        for (int k = 0; k < 4; k++) {
            int nx = x[z] + dx[k];
            int ny = y[z] + dy[k];
            if (id.count({nx, ny})) {
                int p = id[{nx, ny}];
                if (!vis[p]) {
                    dfs(p);
                }
            }
        }
    };

    dfs(0);

    if (count(vis.begin(), vis.end(), 1) != n) {
        return 0;
    }

    vector<int> u, v, a, b;
    for (auto [cx, cy] : pos) {
        if ((cx + cy) % 4 == 0) {
            if (id.count({cx - 1, cy - 1}) && id.count({cx - 1, cy + 1})) {
                u.push_back(id[{cx - 1, cy - 1}]);
                v.push_back(id[{cx - 1, cy + 1}]);
                a.push_back(cx);
                b.push_back(cy);
            } else if (id.count({cx + 1, cy - 1}) && id.count({cx + 1, cy + 1})) {
                u.push_back(id[{cx + 1, cy - 1}]);
                v.push_back(id[{cx + 1, cy + 1}]);
                a.push_back(cx);
                b.push_back(cy);
            }
        } else if ((cx + cy) % 4 == 2) {
            if (id.count({cx - 1, cy - 1}) && id.count({cx + 1, cy - 1})) {
                u.push_back(id[{cx - 1, cy - 1}]);
                v.push_back(id[{cx + 1, cy - 1}]);
                a.push_back(cx);
                b.push_back(cy);
            } else if (id.count({cx - 1, cy + 1}) && id.count({cx + 1, cy + 1})) {
                u.push_back(id[{cx - 1, cy + 1}]);
                v.push_back(id[{cx + 1, cy + 1}]);
                a.push_back(cx);
                b.push_back(cy);
            }
        }
    }

    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