Submission #1233437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233437		Timosh	Fountain Parks (IOI21_parks)	C++20	70 / 100	1481 ms	83136 KiB

parks

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

using namespace std;

vector<pair<int, int>> points(pair<int, int> A, pair<int, int> B)
{
    if (A.first == B.first)
        return {{A.first + 1, (A.second + B.second) / 2}, {A.first - 1, (A.second + B.second) / 2}};
    return {{(A.first + B.first) / 2, B.second + 1}, {(A.first + B.first) / 2, B.second - 1}};
}

int construct_roads(vector<int> x, vector<int> y)
{
    int n = x.size();
    vector<int> u, v, a(n - 1, -1), b(n - 1, -1), vis(n);
    map<pair<int, int>, int> mp, pick;
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++)
        mp[{x[i], y[i]}] = i;
    auto dfs = [&](auto dfs, int x, int y) -> void
    {
        int i = mp[{x, y}];
        vis[i] = 1;
        if (mp.count({x + 2, y}) && !vis[mp[{x + 2, y}]])
            dfs(dfs, x + 2, y), g[i].push_back(mp[{x + 2, y}]);
        if (mp.count({x, y + 2}) && !vis[mp[{x, y + 2}]])
            dfs(dfs, x, y + 2), g[i].push_back(mp[{x, y + 2}]);
        if (mp.count({x - 2, y}) && !vis[mp[{x - 2, y}]])
            dfs(dfs, x - 2, y), g[i].push_back(mp[{x - 2, y}]);
        if (mp.count({x, y - 2}) && !vis[mp[{x, y - 2}]])
            dfs(dfs, x, y - 2), g[i].push_back(mp[{x, y - 2}]);
    };
    dfs(dfs, x[0], y[0]);
    for (auto &i : vis)
        if (i == 0)
            return 0;
    vector<int> bad(n);
    auto change = [&](auto &&change, int i) -> void
    {
        vector<pair<int, int>> pts = points({x[u[i]], y[u[i]]}, {x[v[i]], y[v[i]]});
        for (auto &[x, y] : pts)
        {
            if (!pick.count({x, y}))
            {
                pick[{x, y}] = i, a[i] = x, b[i] = y;
                return;
            }
        }
        for (auto &[x, y] : pts)
        {
            int ind = pick[{x, y}];
            if (!bad[ind])
            {
                bad[ind] = 1;
                change(change, pick[{x, y}]);
                pick[{x, y}] = i, a[i] = x, b[i] = y;
                bad[ind] = 0;
                return;
            }
        }
    };
    int z = 0;
    for (int i = 0; i < n; i++)
        for (auto &j : g[i])
        {
            u.push_back(i);
            v.push_back(j);
            bad[z] = 1;
            change(change, z);
            bad[z] = 0;
            z++;
        }
    // for (int i = 0; i < n - 1; i++)
    //     cout << u[i] << ' ' << v[i] << '\n';
    // cout << '\n';
    // for (int i = 0; i < n - 1; i++)
    //     cout << a[i] << ' ' << b[i] << '\n';
    build(u, v, a, b);
    return 1;
}
// int main()
// {
//     cout << construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});

//     return 0;
// }

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