Submission #677939

#	Time	Username	Problem	Language	Result	Execution time	Memory
677939		APROHACK	Fountain Parks (IOI21_parks)	C++17	15 / 100	482 ms	37248 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int N;
vector<pair<int, int > >node;
map<pair<int, int>, int>mp;
vector<int>u, v, a, b;
int padre[200005];

int findPadre(int k){
    if(padre[k] == k)return k;
    return padre[k] = findPadre(padre[k]);
}

void unir(int p, int q){
    p = findPadre(p);
    q = findPadre(q);
    if(p == q){
        return;
    }
    padre[p] = q;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    N = x.size();
    for(int i = 0 ; i < N ; i ++){
        node.pb({x[i], y[i]});
        mp[{x[i], y[i]}] = i;
        padre[i] = i;
    }

    for(int i = 0 ; i < N ; i++){
        if(node[i].ff == 2 && mp.count({4, node[i].ss})){
            u.pb(i);
            v.pb(mp[{4, node[i].ss}]);
            unir(i, mp[{4, node[i].ss}]);
            a.pb(3);
            b.pb(node[i].ss-1);

        }
        if(mp.count({node[i].ff, node[i].ss-2})){
            if(node[i].ff == 2){
                u.pb(i);
                v.pb(mp[{2, node[i].ss-2}]);
                unir(mp[{2, node[i].ss-2}], i);
                a.pb(1);
                b.pb(node[i].ss-1);
            }else{
                u.pb(i);
                v.pb(mp[{4, node[i].ss-2}]);
                unir(i, mp[{4, node[i].ss-2}]);
                a.pb(5);
                b.pb(node[i].ss-1);
            }
        }
    }
    for(int i =0  ; i < N ; i ++){
        if(findPadre(i) != findPadre(0))return 0;
    }
    build(u, v, a, b);
    return 1;
}

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