제출 #543367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543367		alextodoran	분수 공원 (IOI21_parks)	C++17	100 / 100	1468 ms	146380 KiB

parks

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void build (vector <int> U, vector <int> V, vector <int> A, vector <int> B);

struct Point {
    int x, y;
    int id;
};
bool operator < (const Point &u, const Point &v) {
    return make_pair(u.x, u.y) < make_pair(v.x, v.y);
}
bool operator != (const Point &u, const Point &v) {
    return make_pair(u.x, u.y) != make_pair(v.x, v.y);
}
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int N;
set <Point> fountains;
set <pair <Point, Point>> roads;
set <Point> benches;
set <Point> squares;

map <Point, vector <Point>> adj;

set <Point> seen;
void DFS (Point s) {
    seen.insert(s);
    for (Point t : adj[s]) {
        if (seen.find(t) == seen.end()) {
            if (s.x == t.x) {
                roads.erase(make_pair(Point{s.x - 1, (s.y + t.y) / 2}, Point{s.x + 1, (s.y + t.y) / 2}));
            } else {
                roads.erase(make_pair(Point{(s.x + t.x) / 2, s.y - 1}, Point{(s.x + t.x) / 2, s.y + 1}));
            }
            DFS(t);
        }
    }
}

set <pair <Point, Point>> used;

map <Point, Point> root;
Point findRoot (Point u) {
    if (root.find(u) == root.end()) {
        return u;
    } else {
        return root[u] = findRoot(root[u]);
    }
}
bool join (Point u, Point v) {
    u = findRoot(u);
    v = findRoot(v);
    if (u != v) {
        root[u] = v;
        return true;
    } else {
        return false;
    }
}

int construct_roads (vector <int> X, vector <int> Y) {
    N = (int) X.size();
    for (int i = 0; i < N; i++) {
        fountains.insert(Point{X[i], Y[i], i});
    }
    // Find all usable benches
    for (Point f : fountains) {
        for (int d = 0; d < 2; d++) {
            Point g = Point{f.x + dx[d] * 2, f.y + dy[d] * 2};
            if (fountains.find(g) != fountains.end()) {
                roads.insert(make_pair(f, g));
                if (f.x == g.x) {
                    benches.insert(Point{f.x - 1, (f.y + g.y) / 2});
                    benches.insert(Point{f.x + 1, (f.y + g.y) / 2});
                } else {
                    benches.insert(Point{(f.x + g.x) / 2, g.y - 1});
                    benches.insert(Point{(f.x + g.x) / 2, g.y + 1});
                }
            }
        }
    }
    // Find all squares
    for (Point f : fountains) {
        bool isSquare = true;
        for (int dx : {0, +2}) {
            for (int dy : {0, +2}) {
                isSquare &= (fountains.find(Point{f.x + dx, f.y + dy}) != fountains.end());
            }
        }
        if (isSquare == true) {
            squares.insert(Point{f.x + 1, f.y + 1});
        }
    }
    // Build the dual graph
    for (Point s : squares) {
        for (int d = abs(s.x + s.y) / 2 % 2; d < 4; d += 2) {
            Point t = Point{s.x + dx[d] * 2, s.y + dy[d] * 2};
            if (squares.find(t) == squares.end()) {
                adj[Point{-7, -7}].push_back(t);
            }
            adj[t].push_back(s);
        }
    }
    // Run DFS and cut edges
    DFS(Point{-7, -7});
    for (pair <Point, Point> r : roads) {
        if (join(r.first, r.second) == true) {
            used.insert(r);
        }
    }
    if ((int) used.size() < N - 1) {
        return 0;
    }
    // Build answer
    vector <int> U, V, A, B;
    for (Point b : benches) {
        if (abs(b.x + b.y) / 2 % 2 == 1) {
            for (int dx : {-1, +1}) {
                Point f = Point{b.x + dx, b.y - 1};
                Point g = Point{b.x + dx, b.y + 1};
                if (used.find(make_pair(f, g)) != used.end()) {
                    U.push_back(fountains.find(f)->id);
                    V.push_back(fountains.find(g)->id);
                    A.push_back(b.x);
                    B.push_back(b.y);
                }
            }
        } else {
            for (int dy : {-1, +1}) {
                Point f = Point{b.x - 1, b.y + dy};
                Point g = Point{b.x + 1, b.y + dy};
                if (used.find(make_pair(f, g)) != used.end()) {
                    U.push_back(fountains.find(f)->id);
                    V.push_back(fountains.find(g)->id);
                    A.push_back(b.x);
                    B.push_back(b.y);
                }
            }
        }
    }
    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: 30 / 30