Submission #837428

#	Time	Username	Problem	Language	Result	Execution time	Memory
837428		QwertyPi	Fountain Parks (IOI21_parks)	C++17	70 / 100	1174 ms	85820 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

const int N_MAX = 2e5 + 11;

struct point{
    int x, y;
    bool operator< (const point& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};

struct edge{
    int u, v;
};

int n;
map<point, int> mp;
vector<point> a;

struct DSU{
    int dsu[N_MAX];
    void init(int n){
        for(int i = 0; i < n; i++) dsu[i] = i;
    }
    int f(int x){ return x == dsu[x] ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x), y = f(y); dsu[x] = y; }
} dsu;

vector<edge> construct_tree(){
    vector<edge> ans;
    dsu.init(n);
    vector<int> p; for(int i = 0; i < n; i++) p.push_back(i);
    sort(p.begin(), p.end(), [](int u, int v){ return a[u] < a[v]; });
    for(int j = 0; j < n; j++){
        int i = p[j];
        for(auto [dx, dy] : vector<pair<int, int>>{{0, -2}, {0, 2}, {2, 0}, {-2, 0}}){
            int nx = a[i].x + dx, ny = a[i].y + dy;
            if(mp.count({nx, ny})){
                int v = mp[{nx, ny}];
                if(dsu.f(i) != dsu.f(v)){
                    dsu.g(i, v);
                    ans.push_back({i, v});
                }
            }
        }
    }
    return ans;
}

vector<point> adj(int u, int v){
    assert(abs(a[u].x - a[v].x) + abs(a[u].y - a[v].y) == 2);
    if(a[u].x == a[v].x) return {{a[u].x - 1, (a[u].y + a[v].y) / 2}, {a[u].x + 1, (a[u].y + a[v].y) / 2}};
    else return {{(a[u].x + a[v].x) / 2, a[v].y - 1}, {(a[u].x + a[v].x) / 2, a[v].y + 1}};
}

vector<point> assign_benches(vector<edge> roads){
    vector<point> ans(roads.size());
    map<point, vector<int>> deg;
    set<point> done;
    for(int i = 0; i < (int) roads.size(); i++){
        int u = roads[i].u, v = roads[i].v;
        vector<point> p = adj(u, v);
        deg[p[0]].push_back(i);
        deg[p[1]].push_back(i);
    }
    vector<point> deg_0, deg_1;
    for(auto [p, v] : deg){
        if(v.size() == 0) deg_0.push_back(p);
        if(v.size() == 1) deg_1.push_back(p);
    }
    while(deg.size()){
        while(deg_0.size()) deg.erase(deg_0.back()), deg_0.pop_back();
        while(deg_1.size()){
            point v = deg_1.back(); deg_1.pop_back();
            if(done.count(v) || deg[v].empty()) continue; done.insert(v);

            int r = deg[v][0];
            ans[r] = v;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);
            if(find(all(deg[p[0]]), r) != deg[p[0]].end()) deg[p[0]].erase(find(all(deg[p[0]]), r));
            if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg.count(p[0]) && deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg.count(p[0]) && deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg.count(p[1]) && deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg.count(p[1]) && deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }
        if(deg.size()){
            auto [c, v] = *deg.begin(); 
            if(done.count(c) || deg[c].size() < 2){
                deg.erase(deg.begin());
                continue;
            }
            done.insert(c);
            int r = v[0];
            ans[r] = c;

            int a = roads[r].u, b = roads[r].v;
            vector<point> p = adj(a, b);

            deg[p[0]].clear();
            if(find(all(deg[p[1]]), r) != deg[p[1]].end()) deg[p[1]].erase(find(all(deg[p[1]]), r));

            if(deg[p[0]].size() == 0) deg_0.push_back(p[0]);
            if(deg[p[0]].size() == 1) deg_1.push_back(p[0]);

            if(deg[p[1]].size() == 0) deg_0.push_back(p[1]);
            if(deg[p[1]].size() == 1) deg_1.push_back(p[1]);
        }
    }
    return ans;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = x.size();
    for(int i = 0; i < n; i++){
        a.push_back({x[i], y[i]});
        mp[a[i]] = i;
    }

    vector<edge> edges = construct_tree();
    if((int) edges.size() < n - 1) return 0;
    vector<point> benches = assign_benches(edges);
    vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
    for(int i = 0; i < n - 1; i++){
        u[i] = edges[i].u, v[i] = edges[i].v;
        a[i] = benches[i].x, b[i] = benches[i].y;
    }
    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'std::vector<point> assign_benches(std::vector<edge>)':
parks.cpp:78:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |             if(done.count(v) || deg[v].empty()) continue; done.insert(v);
      |             ^~
parks.cpp:78:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |             if(done.count(v) || deg[v].empty()) continue; done.insert(v);
      |                                                           ^~~~

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