제출 #1198430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198430		HappyCapybara	Fountain Parks (IOI21_parks)	C++17	45 / 100	241 ms	40688 KiB

parks

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

vector<int> p;

int find(int a){
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    p[b] = a;
}

int construct_roads(vector<int> x, vector<int> y){
    int n = x.size();
    map<int,vector<pair<int,int>>> rows, cols;
    for (int i=0; i<n; i++){
        rows[x[i]].push_back({y[i], i});
        cols[y[i]].push_back({x[i], i});
    }
    vector<pair<int,int>> e;
    for (auto [i, v] : cols){
        sort(v.begin(), v.end());
        for (int j=0; j+1<v.size(); j++){
            if (v[j].first+2 == v[j+1].first) e.push_back({v[j].second, v[j+1].second});
        }
    }
    for (auto [i, v] : rows){
        sort(v.begin(), v.end());
        for (int j=0; j+1<v.size(); j++){
            if (v[j].first+2 == v[j+1].first) e.push_back({v[j].second, v[j+1].second});
        }
    }
    p.resize(n);
    for (int i=0; i<n; i++) p[i] = i;
    vector<int> u, v, a, b;
    for (auto [i, j] : e){
        if (find(i) != find(j)){
            u.push_back(i);
            v.push_back(j);
            if (x[i] == x[j]){
                b.push_back((y[i]+y[j])/2);
                int rp = ((x[i]+1)/2+b.back()/2) % 2;
                if (rp) a.push_back(x[i]+1);
                else a.push_back(x[i]-1);
            }
            else {
                a.push_back((x[i]+x[j])/2);
                int up = ((y[i]+1)/2+a.back()/2) % 2;
                if (up) b.push_back(y[i]-1);
                else b.push_back(y[i]+1);
            }
            merge(i, j);
        }
    }
    for (int i=0; i<n; i++){
        if (find(i) != find(0)) return 0;
    }
    build(u, v, a, b);
    return 1;
}

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