Submission #1233430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233430		Timosh	분수 공원 (IOI21_parks)	C++20	0 / 100	0 ms	324 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();
    if (n == 1)
    {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a(n), b(n), 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
    {
        vis[mp[{x, y}]] = 1;
        if (mp.count({x + 2, y}) && !vis[mp[{x + 2, y}]])
            dfs(dfs, x + 2, y), g[mp[{x, y}]].push_back(mp[{x + 2, y}]);
        if (mp.count({x, y + 2}) && !vis[mp[{x, y + 2}]])
            dfs(dfs, x, y + 2), g[mp[{x, y}]].push_back(mp[{x, y + 2}]);
        if (mp.count({x - 2, y}) && !vis[mp[{x - 2, y}]])
            dfs(dfs, x - 2, y), g[mp[{x, y}]].push_back(mp[{x - 2, y}]);
        if (mp.count({x, y - 2}) && !vis[mp[{x, y - 2}]])
            dfs(dfs, x, y - 2), g[mp[{x, y}]].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)
        {
            if (!bad[pick[{x, y}]])
            {
                bad[pick[{x, y}]] = 1;
                change(change, pick[{x, y}]);
                pick[{x, y}] = i, a[i] = x, b[i] = y;
                bad[pick[{x, y}]] = 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++;
        }
    build(u, v, a, b);
    return 1;
}

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