Submission #623459

#	Time	Username	Problem	Language	Result	Execution time	Memory
623459		cheissmart	Fountain Parks (IOI21_parks)	C++17	15 / 100	466 ms	78228 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, b;
    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 X++;
        } else { // horizontal
            Y--;
        }
        a.PB(X), b.PB(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