제출 #439954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
439954		cheeheng	분수 공원 (IOI21_parks)	C++17	55 / 100	1369 ms	149912 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};

vector<int> AdjList[200005];
ii EdgeList[800005];
ii EdgeList2[800005];
map<ii, int> indx;
map<ii, int> indxEdge;
map<ii, int> indxBench;

vector<int> AdjListBench[800005];
set<int> AdjListRoad[200005];
int degBench[800005];
ii benchXY[800005];

struct UnionFind{
    vector<int> p;
    vector<int> rank1;
    void init(int n){
        p.assign(n, 0);
        rank1.assign(n, 0);
        for(int i = 0; i < n; i ++){
            p[i] = i;
            rank1[i] = 0;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        int x = findSet(i);
        int y = findSet(j);

        if(x != y){
            if(rank1[x] > rank1[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank1[x] == rank1[y]){
                    rank1[y] ++;
                }
            }
        }
    }
};

int p[200005];

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = (int)x.size();
    if (n == 1) {
        build({}, {}, {}, {});
        return 1;
    }

    vector<int> U(n-1);
    vector<int> V(n-1);
    vector<int> A(n-1);
    vector<int> B(n-1);

    for(int i = 0; i < n; i ++){
        indx[ii(x[i], y[i])] = i;
    }

    int cnt3 = 0;
    for(pair<ii, int> temp: indx){
        p[cnt3 ++] = temp.second;
    }

    int m = 0;
    for(int i = 0; i < n; i ++){
        int i2 = p[i];
        for(int k = 0; k < 4; k ++){
            int nx = x[i2] + 2*dx[k];
            int ny = y[i2] + 2*dy[k];

            if(indx.find(ii(nx, ny)) != indx.end()){
                int j = indx[ii(nx, ny)];
                EdgeList[m ++] = ii(i2, j);
            }
        }
    }

    UnionFind* uf = new UnionFind();
    uf->init(n);

    int cnt = 0;
    for(int i = 0; i < m; i ++){
        int u, v;
        tie(u, v) = EdgeList[i];
        if(!uf->isSameSet(u, v)){
            uf->unionSet(u, v);
            AdjList[u].push_back(v);
            AdjList[v].push_back(u);
            EdgeList2[cnt] = ii(u, v);
            indxEdge[ii(u, v)] = cnt;
            cnt ++;
        }
    }

    if(cnt != n-1){
        return 0;
    }

    int benches = 0;
    memset(degBench, 0, sizeof(degBench));
    for(int i = 0; i < n-1; i ++){
        int u, v;
        tie(u, v) = EdgeList2[i];
        int x2 = (x[u] + x[v])/2;
        int y2 = (y[u] + y[v])/2;

        for(int k = 0; k < 4; k ++){
            int nx = x2 + dx[k];
            int ny = y2 + dy[k];
            if(nx%2 == 1 && ny%2 == 1){
                int indx2 = benches;
                if(indxBench.find(ii(nx, ny)) != indxBench.end()){
                    indx2 = indxBench[ii(nx, ny)];
                }else{
                    benchXY[benches] = ii(nx, ny);
                    indxBench[ii(nx, ny)] = benches;
                    //printf("bench %d; (%d, %d)\n", benches, nx, ny);
                    benches ++;
                }

                AdjListBench[indx2].push_back(i);
                AdjListRoad[i].insert(indx2);
                //printf("road %d; bench %d\n", i, indx2);
                degBench[i] ++;
            }
        }
    }

    set<ii> s;
    for(int i = 0; i < n-1; i ++){
        if(degBench[i] > 0){
            s.insert(ii(degBench[i], i));
        }
    }

    int cnt2 = 0;
    while(!s.empty()){
        ii temp = *s.begin();
        int indx = temp.second;
        int bench = *(--AdjListRoad[indx].end());
        //printf("road %d matched to bench %d\n", indx, bench);

        tie(U[cnt2], V[cnt2]) = EdgeList2[indx];
        tie(A[cnt2], B[cnt2]) = benchXY[bench];
        cnt2 ++;

        for(int road: AdjListBench[bench]){
            //assert(s.count(ii(degBench[road], road)));
            s.erase(ii(degBench[road], road));
            degBench[road] --;
            AdjListRoad[road].erase(bench);

            if(degBench[road] > 0 && road != indx){
                s.insert(ii(degBench[road], road));
            }
        }
    }

    if(cnt2 == n-1){
        build(U, V, A, B);
        return 1;
    }else{
        return 0;
    }
}

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