제출 #435639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435639		79brue	분수 공원 (IOI21_parks)	C++17	70 / 100	1542 ms	148232 KiB

parks

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

using namespace std;

typedef long long ll;

struct Edge{
    int u, v, idx;
    Edge(){}
    Edge(int u, int v, int idx): u(u), v(v), idx(idx){}

    bool operator==(const Edge &r)const{
        return idx==r.idx;
    }
};

struct dat{
    int x, y;
    vector<Edge> vec;
    dat(){}
    dat(int x, int y, vector<Edge> vec): x(x), y(y), vec(vec){}

    bool operator<(const dat &r)const{
        if(vec.size() != r.vec.size()) return vec.size() < r.vec.size();
        return make_pair(x, y) < make_pair(r.x, r.y);
    }
};

int xx[]={1, 0, -1, 0}, yy[]={0, 1, 0, -1};

int n;
pair<int, int> arr[200002];
map<pair<int, int>, int> idx;

int par[200002];
int edgeU[200002], edgeV[200002], edgeCnt;
int edgeA[200002], edgeB[200002];
vector<pair<int, int> > link[200002];
map<pair<int, int>, vector<Edge> > mp;
set<dat> st;

int find(int x){
    if(x==par[x]) return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y){
    x = find(x), y = find(y);
    par[y] = x;
}

void dfs(int u){
    int x = arr[u].first, y = arr[u].second;
    for(int d=0; d<4; d++){
        int tx = x+xx[d]+xx[d], ty = y+yy[d]+yy[d];
        if(idx.find(make_pair(tx, ty)) == idx.end()) continue;
        int tmp = idx[make_pair(tx, ty)];
        if(find(u) == find(tmp)) continue;

        edgeU[edgeCnt] = u, edgeV[edgeCnt] = tmp;
        if(x == tx){
            mp[make_pair(x+1, y+yy[d])].push_back(Edge(u, tmp, edgeCnt));
            mp[make_pair(x-1, y+yy[d])].push_back(Edge(u, tmp, edgeCnt));
            link[edgeCnt].push_back(make_pair(x+1, y+yy[d]));
            link[edgeCnt].push_back(make_pair(x-1, y+yy[d]));
        }
        else{
            mp[make_pair(x+xx[d], y+1)].push_back(Edge(u, tmp, edgeCnt));
            mp[make_pair(x+xx[d], y-1)].push_back(Edge(u, tmp, edgeCnt));
            link[edgeCnt].push_back(make_pair(x+xx[d], y-1));
            link[edgeCnt].push_back(make_pair(x+xx[d], y+1));
        }
        edgeCnt++;

        merge(u, tmp);
        dfs(tmp);
    }
}

int construct_roads(vector<int> x, vector<int> y) {
    n = (int)x.size();
    for(int i=0; i<n; i++){
        arr[i] = make_pair(x[i], y[i]);
        par[i] = i;
        idx[arr[i]] = i;
    }

    int start = min_element(arr, arr+n) - arr;
    dfs(start);
    for(int i=0; i<n; i++){
        if(find(i) != find(0)) return 0;
    }

    for(auto p: mp){
        st.insert(dat(p.first.first, p.first.second, p.second));
    }
    while(!st.empty()){
        dat tmp = *st.begin(); st.erase(st.begin());
        if(tmp.vec.empty()) continue;
        Edge edge = tmp.vec[0];
        edgeA[edge.idx] = tmp.x;
        edgeB[edge.idx] = tmp.y;
        for(auto p: link[edge.idx]){
            if(p.first == tmp.x && p.second == tmp.y) continue;
            st.erase(dat(p.first, p.second, mp[p]));
            auto it = find(mp[p].begin(), mp[p].end(), Edge(edgeU[edge.idx], edgeV[edge.idx], edge.idx));
            if(it == mp[p].end()) continue;
            mp[p].erase(it);
            st.insert(dat(p.first, p.second, mp[p]));
        }
    }

    build(vector<int>(edgeU, edgeU+n-1), vector<int>(edgeV, edgeV+n-1), vector<int>(edgeA, edgeA+n-1), vector<int>(edgeB, edgeB+n-1));
    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