Submission #1097206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097206		abczz	Fountain Parks (IOI21_parks)	C++17	70 / 100	1524 ms	142376 KiB

parks

#include "parks.h"
#include <iostream>
#include <map>
#include <array>
#include <queue>
#define ll long long
 
using namespace std;
 
map <array<ll, 2>, ll> mp;
map <array<ll, 2>, ll> visited;
map <array<ll, 2>, ll> pt;
map <array<ll, 3>, ll> edge;
queue <array<ll, 2>> Q;
vector <int> U, V, A, B;
ll dj[4][2] = {-1, -1, -1, 1, 1, 1, 1, -1}, dk[4][2] = {-2, 0, 0, 2, 2, 0, 0, -2};
 
void dfs(ll u, ll v) {
    ++visited[{u, v}];
    for (int i=0; i<4; ++i) {
        ll nx = u + dk[i][0], ny = v + dk[i][1];
        if (pt.count({nx, ny}) && !visited.count({nx, ny})) dfs(nx, ny);
    }
}
 
void solve(ll u, ll v) {
    for (int i=0; i<4; ++i) {
        if (edge.count({u, v, i})) {
            if (visited.count({u, v})) break;
            ++visited[{u, v}];
            U.push_back(pt[{u + dj[i][0], v + dj[i][1]}]);
            V.push_back(pt[{u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]}]);
            A.push_back(u);
            B.push_back(v);
            edge.erase({u, v, i});
            edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
            solve(u + dk[i][0], v + dk[i][1]);
            break;
        }
    }
}
 
int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll n = x.size();
    for (int i=0; i<n; ++i) {
        pt[{x[i], y[i]}] = i;
        for (int j=0; j<4; ++j) {
            ll nx = x[i] + dj[j][0], ny = y[i] + dj[j][1];
            ++mp[{nx, ny}];
        }
    }
    dfs(x[0], y[0]);
    if (visited.size() != pt.size()) return 0;
    for (auto it = mp.begin(); it != mp.end();) {
        auto nx = next(it);
        auto [u, v] = it->first;
        ll tot = 0;
        for (int i=0; i<4; ++i) {
            if (pt.count({u + dj[i][0], v + dj[i][1]}) && pt.count({u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]})) {
                ++tot;
                ++edge[{u, v, i}];
            }
        }
        mp[{u, v}] = tot;
        if (tot == 0) mp.erase(it);
        else if (tot == 1) Q.push({u, v});
        it = nx;
    }
    while (!Q.empty()) {
        auto [u, v] = Q.front();
        Q.pop();
        if (!mp.count({u, v})) continue;
        for (int i=0; i<4; ++i) {
            if (edge.count({u, v, i})) {
                U.push_back(pt[{u + dj[i][0], v + dj[i][1]}]);
                V.push_back(pt[{u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]}]);
                edge.erase({u, v, i});
                edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
                --mp[{u + dk[i][0], v + dk[i][1]}];
                if (mp[{u + dk[i][0], v + dk[i][1]}] == 1) Q.push({u + dk[i][0], v + dk[i][1]});
                else if (mp[{u + dk[i][0], v + dk[i][1]}] == 0) mp.erase({u + dk[i][0], v + dk[i][1]});
            }
        }
        mp.erase({u, v});
        A.push_back(u);
        B.push_back(v);
    }
    for (auto [y, z] : mp) {
        auto [u, v] = y;
        if (z == 3) Q.push({u, v});
    }
    while (!Q.empty()) {
        auto [u, v] = Q.front();
        Q.pop();
        for (int i=0; i<4; ++i) {
            if (mp[{u + dk[i][0], v + dk[i][1]}] == 4) {
                edge.erase({u, v, i});
                edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
                --mp[{u + dk[i][0], v + dk[i][1]}];
                Q.push({u + dk[i][0], v + dk[i][1]});
            }
        }
    }
    for (auto [y, z] : mp) {
        if (z == 4) return 0;
    }
    visited.clear();
    for (auto [y, z] : mp) {
        auto [u, v] = y;
        solve(u, v);
    }
    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: 0 / 30