Submission #623470

#	Time	Username	Problem	Language	Result	Execution time	Memory
623470		cheissmart	Fountain Parks (IOI21_parks)	C++17	15 / 100	508 ms	133692 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

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

int construct_roads(vi x, vi y) {
    int n = SZ(x);
    map<pi, int> mp;
    for(int i = 0; i < n; i++)
        mp[{x[i], y[i]}] = i;

    V<pi> edges;
    set<pi> vis;
    function<void(int, int)> dfs = [&] (int X, int Y) {
        vis.insert({X, Y});
        for(int i = 0; i < 4; i++) {
            int xx = X + dx[i], yy = Y + dy[i];
            if(mp.count({xx, yy}) && !vis.count({xx, yy})) {
                edges.EB(mp[{X, Y}], mp[{xx, yy}]);
                dfs(xx, yy);
            }
        }
    };
    dfs(x[0], y[0]);
    if(SZ(vis) != n) return 0;

    vi u, v, a(n - 1), b(n - 1);
    V<array<int, 3>> todo;
    set<pi> used;
    for(int i = 0; i < n - 1; i++) {
        u.PB(edges[i].F), v.PB(edges[i].S);
        int X = (x[edges[i].F] + x[edges[i].S]) / 2;
        int Y = (y[edges[i].F] + y[edges[i].S]) / 2;
        if(x[edges[i].F] == x[edges[i].S]) { // vertical
            if(X == 2) {
                X--;
            } else if(X == 6) {
                X++;
            } else {
                todo.PB({i, X, Y});
            }
        } else { // horizontal
            if(X == 3) {
                Y++;
            } else {
                assert(X == 5);
                Y--;
            }
        }
        a[i] = X, b[i] = Y;
        used.insert({X, Y});
    }
    for(auto[i, X, Y]:todo) {
        assert(!used.count({X - 1, Y}) || !used.count({X + 1, Y}));
        if(!used.count({X - 1, Y})) {
            X--;
        } else {
            X++;
        }
        a[i] = X, b[i] = Y;
    }
    build(u, v, a, b);
    return 1;
}

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