Submission #836858

#	Time	Username	Problem	Language	Result	Execution time	Memory
836858		ma_moutahid	Fountain Parks (IOI21_parks)	C++17	5 / 100	227 ms	43644 KiB

parks

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

#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vp vector<pi>

vi d;
vi h;
int parent(int x){
    if(d[x]==x)return x;
    return d[x]=parent(d[x]);
}
void connect(int a, int b){
    a=parent(a);
    b=parent(b);
    if(h[a]<h[b])swap(a,b);
    if(h[a]==h[b])h[a]++;
    d[b]=a;
}



int construct_roads(std::vector<int> x, std::vector<int> y) {
    //bsmllah
    int n=x.size();
    d.resize(n);for(int i=0;i<n;i++)d[i]=i;
    h.resize(n);
    vi u;
    vi v;
    vi a;
    vi b;

    map<pi,int>f;
    for(int i=0;i<n;i++){
        f.insert(make_pair(pi(x[i],y[i]),i));
    }
    vii k(4, vi(200001,-1));
    for(int i=0;i<n;i++){
        k[x[i]/2][y[i]]=i;
        if(x[i]==4){
            continue;
        }
        auto itr=f.find(pi(x[i],y[i]+2));
        if(itr!=f.end()){
            u.push_back(i);
            v.push_back(itr->second);
            a.push_back(x[i]+(x[i]>3?1:-1));
            b.push_back(y[i]+1);
            connect(i,itr->second);
        }
    }
    if(k[2][2]!=-1){
        if(k[1][2]!=-1){
            u.push_back(k[1][2]);
            v.push_back(k[2][2]);
            connect(k[1][2],k[2][2]);
            a.push_back(3);
            b.push_back(1);
        }
        if(k[3][2]!=-1){
            u.push_back(k[3][2]);
            v.push_back(k[2][2]);
            connect(k[3][2],k[2][2]);
            a.push_back(5);
            b.push_back(1);
        }
    }
    for(int i=4;i<200001;i+=2){
        if(k[2][i]==-1)continue;
        if(k[2][i-2]==-1){
            if(k[1][i]!=-1){
                u.push_back(k[1][i]);
                v.push_back(k[2][i]);
                a.push_back(3);
                b.push_back(i-1);
                connect(k[1][i],k[2][i]);
            }
            if(k[3][i]!=-1){
                u.push_back(k[3][i]);
                v.push_back(k[2][i]);
                a.push_back(5);
                b.push_back(i-1);
                connect(k[3][i],k[2][i]);
            }
            continue;
        }
        u.push_back(k[2][i]);
        v.push_back(k[2][i-2]);
        b.push_back(i-1);
        if(i%4){
            a.push_back(5);
        }
        else{
            a.push_back(3);
        }
        connect(k[2][i],k[2][i-2]);
        if(k[3][i-2]==1 && k[3][i]!=-1){
            u.push_back(k[3][i]);
            v.push_back(k[2][i]);
            a.push_back(5);
            if(i%4){
                b.push_back(i+1);
            }
            else {
                b.push_back(i-1);
            }
            connect(k[3][i],k[2][i]);
        }
        if(k[1][i-2]==1 && k[1][i]!=-1){
            u.push_back(k[1][i]);
            v.push_back(k[2][i]);
            a.push_back(3);
            if(i%4){
                b.push_back(i-1);
            }
            else {
                b.push_back(i+1);
            }
            connect(k[1][i],k[2][i]);
        }
        
    }


    for(int i=0;i<n;i++){
        if(parent(d[i])!=parent(d[0]))return 0;
    }

    build(u,v,a,b);
    return 1;
}

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