Submission #818394

#	Time	Username	Problem	Language	Result	Execution time	Memory
818394		jophyyjh	Fountain Parks (IOI21_parks)	C++17	70 / 100	1192 ms	72204 KiB

parks

/**
 * (Just a test)
 * 
 * Time Complexity: O(n * log(n))       (Kruskal, bipartite graph, BFS, implementation)
 * Implementation 0.9               (Just a test)
*/

#include <bits/stdc++.h>
#include "parks.h"

typedef std::vector<int>    vec;

struct DSU {
    vec set, rank;
    DSU(int n) {
        set.resize(n);
        rank.resize(n);
        for (int k = 0; k < n; k++)
            set[k] = k, rank[k] = 1;
    }
    inline int find(int k) {
        if (set[k] == k)
            return k;
        return set[k] = find(set[k]);
    }
    bool merge(int a, int b) {
        a = find(a), b = find(b);
        if (a == b)
            return false;
        if (rank[b] > rank[a])
            std::swap(a, b);
        set[b] = a, rank[a] += rank[b];
        return true;
    }
};


struct pos_t {
    int x, y;
};

inline bool operator<(const pos_t& p1, const pos_t& p2) {
    return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}

int construct_roads(vec x, vec y) {
    int n = x.size();
    std::map<pos_t, int> map;
    for (int k = 0; k < n; k++)
        map[{x[k], y[k]}] = k;
    
    DSU dsu(n);
    vec u(n - 1), v(n - 1);
    int ans_pt = 0;
    std::map<pos_t, vec> road_ls;
    for (int k = 0; k < n; k++) {
        for (int d = -1; d <= 1; d += 2) {
            pos_t new_pos = {x[k], y[k] + 2 * d};
            if (map.find(new_pos) == map.end())
                continue;
            int l = map[new_pos];
            if (dsu.merge(k, l)) {
                u[ans_pt] = k, v[ans_pt] = l;
                road_ls[{x[k] - 1, y[k] + d}].push_back(ans_pt);
                road_ls[{x[k] + 1, y[k] + d}].push_back(ans_pt);
                ans_pt++;
            }
        }
    }
    vec order(n);
    for (int i = 0; i < n; i++)
        order[i] = i;
    std::sort(order.begin(), order.end(),
              [&](int o1, int o2) {
                  return y[o1] > y[o2];
              });
    for (int k : order) {
        for (int d = -1; d <= 1; d += 2) {
            pos_t new_pos = {x[k] + 2 * d, y[k]};
            if (map.find(new_pos) == map.end())
                continue;
            int l = map[new_pos];
            if (dsu.merge(k, l)) {
                u[ans_pt] = k, v[ans_pt] = l;
                road_ls[{x[k] + d, y[k] + 1}].push_back(ans_pt);
                road_ls[{x[k] + d, y[k] - 1}].push_back(ans_pt);
                ans_pt++;
            }
        }
    }
    if (ans_pt < n - 1)
        return 0;
    assert(ans_pt == n - 1);

    vec bench_x(n - 1, -1), bench_y(n - 1, -1);
    std::queue<int> bfs_queue;
    for (int start = n - 2; start >= 0; start--) {
        if (bench_x[start] != -1)
            continue;
        int s_u = u[start], s_v = v[start];
        if (y[s_u] == y[s_v])       // horizontal
            bench_x[start] = (x[s_u] + x[s_v]) / 2, bench_y[start] = y[s_u] + 1;    // up
        else
            bench_x[start] = x[s_u] + 1, bench_y[start] = (y[s_u] + y[s_v]) / 2;
        bfs_queue.push(start);
        while (!bfs_queue.empty()) {
            int t = bfs_queue.front(), bx = bench_x[t], by = bench_y[t];
            bfs_queue.pop();
            assert(bx != -1 && by != -1);
            for (int nr : road_ls[{bx, by}]) {
                if (bench_x[nr] != -1)
                    continue;
                bench_x[nr] = x[u[nr]] + x[v[nr]] - bx;
                bench_y[nr] = y[u[nr]] + y[v[nr]] - by;
                bfs_queue.push(nr);
            }
        }
    }
    build(u, v, bench_x, bench_y);
    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