제출 #435702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435702		talant117408	Fountain Parks (IOI21_parks)	C++17	55 / 100	1162 ms	90940 KiB

parks

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

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

const int MAXN = 6e5+7;
vector <int> graph[MAXN];
int N, RN, BN, degree[MAXN], parent[MAXN];
bool used[MAXN];
int link[MAXN], saizu[MAXN];
int x[MAXN], y[MAXN];
pii roads[MAXN];
vector <pii> benches;

int find(int n) {
    if (n == link[n]) return n;
    return link[n] = find(link[n]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (saizu[a] < saizu[b]) swap(a, b);
    saizu[a] += saizu[b];
    link[b] = a;
}

bool same(int a, int b) {
    return find(a) == find(b);
}

void dfs(int v) {
    used[v] = 1;
    for (auto to : graph[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

void dfs2(int v, int p) {
    parent[v] = p;
    used[v] = 1;
    for (auto to : graph[v]) {
        if (used[to]) continue;
        degree[v]++;
        dfs2(to, v);
    }
}

int construct_roads(vector<int> X, vector<int> Y) {
    N = sz(X);
    
    if (N == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    
    for (int i = 0; i < N; i++) {
        link[i] = i;
        saizu[i] = 1;
        x[i] = X[i];
        y[i] = Y[i];
    }
    X.clear(); Y.clear();
    
    //***************** get roads and benches *****************
    vector <pair <pii, int>> tmp;
    vector <pii> edges;
    set <pii> tmpBenches;
    for (int i = 0; i < N; i++) {
        tmp.pb(mp(mp(x[i], y[i]), i));
    }
    sort(all(tmp));
    for (int i = 0; i < N; i++) {
        auto it = lb(all(tmp), mp(mp(x[i]-2, y[i]), 0));
        if (it != tmp.end() && (*it).first == mp(x[i]-2, y[i])) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i]+2, y[i]), 0));
        if (it != tmp.end() && (*it).first == mp(x[i]+2, y[i])) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i], y[i]-2), 0));
        if (it != tmp.end() && (*it).first == mp(x[i], y[i]-2)) {
            edges.pb(mp(i, (*it).second));
        }
        it = lb(all(tmp), mp(mp(x[i], y[i]+2), 0));
        if (it != tmp.end() && (*it).first == mp(x[i], y[i]+2)) {
            edges.pb(mp(i, (*it).second));
        }
    }
    for (auto &to : edges) {
        if (mp(x[to.first], y[to.first]) > mp(x[to.second], y[to.second])) {
            swap(to.first, to.second);
        }
        if (!same(to.first, to.second)) {
            unite(to.first, to.second);
            graph[to.first].pb(to.second);
            graph[to.second].pb(to.first);
            roads[RN++] = mp(to.first, to.second);
            if (x[to.first] == x[to.second]) {
                tmpBenches.insert(mp(x[to.first]-1, y[to.first]+1));
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
            }
            else {
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]+1));
                tmpBenches.insert(mp(x[to.first]+1, y[to.first]-1));
            }
        }
    }
    for (auto to : tmpBenches) {
        benches.pb(to);
    }
    BN = sz(benches);
    //***************** get roads and benches *****************
    
    //***************** check if connected ***************** 
    dfs(0);
    bool flag = 1;
    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            flag = 0;
            break;
        }
    }
    if (!flag) {
        return 0;
    }
    for (int i = 0; i < RN+BN; i++) {
        link[i] = i;
        saizu[i] = 1;
        used[i] = 0;
        graph[i].clear();
    }
    edges.clear();
    //***************** check if connected ***************** 
    
    //***************** create a new graph *****************
    for (int i = 0; i < RN; i++) {
        auto a = roads[i].first, b = roads[i].second;
        if (x[a] == x[b]) {
            auto it = lb(all(benches), mp(x[a]-1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
            it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
        }
        else {
            auto it = lb(all(benches), mp(x[a]+1, y[a]-1))-benches.begin();
            edges.pb(mp(i, it+RN));
            it = lb(all(benches), mp(x[a]+1, y[a]+1))-benches.begin();
            edges.pb(mp(i, it+RN));
        }
    }
    for (auto to : edges) {
        if (!same(to.first, to.second)) {
            unite(to.first, to.second);
            graph[to.first].pb(to.second);
            graph[to.second].pb(to.first);
        }
    }
    for (int i = 0; i < RN; i++) {
        if (!used[i] && sz(graph[i]) == 1) {
            dfs2(i, i);
        }
    }
    for (int i = 0; i < RN; i++) {
        if (!used[i]) {
            dfs2(i, i);
        }
    }
    for (int i = 0; i < RN+BN; i++) {
        used[i] = 0;
    }
    //***************** create a new graph *****************
    
    //***************** get the answer *****************
    vector <int> _u, _v, _x, _y;
    queue <int> K;
    for (int i = RN; i < RN+BN; i++) {
        if (!degree[i]) {
            K.push(i);
        }
    }
    while (!K.empty()) {
        auto v = K.front(); K.pop();
        if (!used[v] && !used[parent[v]]) {
            used[v] = 1;
            used[parent[v]] = 1;
            _u.pb(roads[parent[v]].first);
            _v.pb(roads[parent[v]].second);
            _x.pb(benches[v-RN].first);
            _y.pb(benches[v-RN].second);
            v = parent[parent[v]];
            if (v >= RN) {
                degree[v]--;
                if (!used[v] && !degree[v]) {
                    K.push(v);
                }
            }
        }
    }
    build(_u, _v, _x, _y);
    //***************** get the answer *****************
    
    return 1;
}

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