제출 #1243274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243274		guanex	Fountain Parks (IOI21_parks)	C++20	30 / 100	232 ms	29328 KiB

parks

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

using namespace std;

int f[200005];
int len[200005];

int ffather(int no){
    if(f[no] == no){
        return no;
    }
    return f[no] = ffather(f[no]);
}

bool joint(int u, int v){
    u = ffather(u);
    v = ffather(v);
    if(u == v)return 1;
    return 0;
}

void join(int u, int v){
    u = ffather(u);
    v = ffather(v);
    if(len[u] < len[v]){
        swap(u, v);
    }
    f[v] = u;
    len[u] += len[v];
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    vector<pair<int, int>> two;
    vector<pair<int, int>> four;
    vector<pair<int, int>> six;
    map<pair<int, int>, int> m;
    for(int i = 0; i < (int)x.size(); ++i){
        f[i] = i;
        len[i] = 1;
        m[{x[i], y[i]}] = i;
        if(x[i] == 2){
            two.push_back({y[i], i});
        }else if(x[i] == 4){
            four.push_back({y[i], i});
        }else{
            six.push_back({y[i], i});
        }
    }
    sort(two.begin(), two.end());
    sort(four.begin(), four.end());
    sort(six.begin(), six.end());
    vector<int> u, v, a, b;
    for(int i = 0; i < (int)two.size()-1; ++i){
        if(two[i].first == two[i+1].first - 2){
            join(m[{2, two[i].first}], m[{2, two[i+1].first}]);
            u.push_back(two[i].second);
            v.push_back(two[i+1].second);
            a.push_back(1);
            b.push_back(two[i].first+1);
        }
    }
    for(int i = 0; i < (int)six.size()-1; ++i){
        //cout << "hi" << endl;
        if(six[i].first == six[i+1].first - 2){
            join(m[{6, six[i].first}], m[{6, six[i+1].first}]);         
            u.push_back(six[i].second);
            v.push_back(six[i+1].second);
            a.push_back(7);
            b.push_back(six[i].first+1);
        }
    }
    for(int i = 0; i < (int)four.size(); ++i){
        if(i == (int)four.size()-1 || four[i].first != four[i+1].first-2){
            if(m.count({2, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}])){
                join(m[{2, four[i].first}], m[{4, four[i].first}]);
                u.push_back(four[i].second);
                v.push_back(m[{2, four[i].first}]);
                a.push_back(3);
                b.push_back(four[i].first+1);
            }
            if(m.count({6, four[i].first}) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
                join(m[{6, four[i].first}], m[{4, four[i].first}]);
                u.push_back(four[i].second);
                v.push_back(m[{6, four[i].first}]);
                a.push_back(5);
                b.push_back(four[i].first+1);
            }
            continue;
        }
        //cout << four[i].second << endl;
        if(m.count({2, four[i].first}) && m.count({6, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}]) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
            join(m[{6, four[i].first}], m[{4, four[i].first}]);
            join(m[{2, four[i].first}], m[{4, four[i].first}]);
            join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
            u.push_back(four[i].second);
            v.push_back(four[i+1].second);
            a.push_back(3);
            b.push_back(four[i].first+1);
            
            u.push_back(four[i].second);
            v.push_back(m[{2, four[i].first}]);
            a.push_back(3);
            b.push_back(four[i].first-1);
            
            u.push_back(four[i].second);
            v.push_back(m[{6, four[i].first}]);
            a.push_back(5);
            b.push_back(four[i].first+1);
            
        }else if(m.count({2, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}])){
            join(m[{2, four[i].first}], m[{4, four[i].first}]);
            join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
            
            u.push_back(four[i].second);
            v.push_back(four[i+1].second);
            a.push_back(5);
            b.push_back(four[i].first+1);
            
            u.push_back(four[i].second);
            v.push_back(m[{2, four[i].first}]);
            a.push_back(3);
            b.push_back(four[i].first+1);
            
        }else if(m.count({6, four[i].first}) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
            join(m[{6, four[i].first}], m[{4, four[i].first}]);
            join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
            
            u.push_back(four[i].second);
            v.push_back(four[i+1].second);
            a.push_back(3);
            b.push_back(four[i].first+1);
            
            u.push_back(four[i].second);
            v.push_back(m[{6, four[i].first}]);
            a.push_back(5);
            b.push_back(four[i].first+1);
        }else{
            join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
            u.push_back(four[i].second);
            v.push_back(four[i+1].second);
            a.push_back(5);
            b.push_back(four[i].first+1);
        }
    }
    int cnt = 0;
    for(int i = 0; i < (int)x.size(); ++i){
        if(f[i] == i){
            cnt++;
        }
    }
    if((int)u.size() < (int)x.size()-1 || cnt != 1){
        return 0;
    }
    build(u, v, a, b);
    return 1;
}

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