Submission #1217691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217691		guagua0407	Fountain Parks (IOI21_parks)	C++20	5 / 100	169 ms	30844 KiB

parks

#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    struct DSU{
        vector<int> e;
        DSU(int n){
            e=vector<int>(n,-1);
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        int sz(int x){
            return -e[find(x)];
        }
        bool unite(int a,int b){
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            return true;
        }
    };
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    map<int,map<int,int>> mp;
    map<int,int> cnt;
    int n=(int)x.size();
    for(int i=0;i<n;i++){
        mp[y[i]][x[i]]=i+1;
        cnt[y[i]]++;
    }
    vector<int> ys;
    for(int i=0;i<n;i++){
        ys.push_back(y[i]);
    }
    sort(all(ys));
    ys.resize(unique(all(ys))-ys.begin());
    vector<int> u,v,a,b;
    int cnt2=0;
    for(auto Y:ys){
        if(cnt[Y-2]==0){
            cnt2++;
            continue;
        }
        bool tf=false;
        if(mp[Y][2]!=0 and mp[Y-2][2]!=0){
            u.push_back(mp[Y-2][2]-1);
            v.push_back(mp[Y][2]-1);
            a.push_back(1);
            b.push_back(Y-1);
            tf=true;
        }
        else if(mp[Y][6]!=0 and mp[Y-2][6]!=0){
            u.push_back(mp[Y-2][6]-1);
            v.push_back(mp[Y][6]-1);
            a.push_back(7);
            b.push_back(Y-1);
            tf=true;
        }
        if(tf){
            if(mp[Y][2]!=0 and mp[Y][4]!=0){
                u.push_back(mp[Y][2]-1);
                v.push_back(mp[Y][4]-1);
                a.push_back(3);
                b.push_back(Y-1);
                //tf=true;
            }
            if(mp[Y][4]!=0 and mp[Y][6]!=0){
                u.push_back(mp[Y][4]-1);
                v.push_back(mp[Y][6]-1);
                a.push_back(5);
                b.push_back(Y-1);
                //tf=true;
            }
            continue;
        }
        if(mp[Y][4]==0 or mp[Y-2][4]==0){
            return 0;
        }
        if(mp[Y][2]!=0 and mp[Y][6]!=0){
            u.push_back(mp[Y-2][4]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(1);
            b.push_back(Y-1);
            u.push_back(mp[Y][4]-1);
            v.push_back(mp[Y][6]-1);
            a.push_back(5);
            b.push_back(Y-1);
            u.push_back(mp[Y][2]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(1);
            b.push_back(Y+1);
        }
        else if(mp[Y][2]!=0){
            u.push_back(mp[Y-2][4]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(5);
            b.push_back(Y-1);
            u.push_back(mp[Y][2]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(1);
            b.push_back(Y-1);
        }
        else if(mp[Y][6]!=0){
            u.push_back(mp[Y-2][4]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(1);
            b.push_back(Y-1);
            u.push_back(mp[Y][4]-1);
            v.push_back(mp[Y][6]-1);
            a.push_back(5);
            b.push_back(Y-1);
        }
        else{
            u.push_back(mp[Y-2][4]-1);
            v.push_back(mp[Y][4]-1);
            a.push_back(5);
            b.push_back(Y-1);
        }
    }
    //if(cnt2>1) return 0;
    /*vector<pair<int,int>> e;
    for(int i=0;i<n;i++){
        if(mp.find({x[i]-2,y[i]})!=mp.end()){
            e.push_back({mp[{x[i]-2,y[i]}],i});
        }
        if(x[i]==2 or x[i]==6){
            if(mp.find({x[i],y[i]-2})!=mp.end()){
                e.push_back({mp[{x[i],y[i]-2}],i});
            }
        }
    }*/
    DSU dsu(n);
    for(int i=0;i<(int)u.size();i++){
        //cout<<v.f<<' '<<v.s<<'\n';
        dsu.unite(u[i],v[i]);
    }
    if(dsu.sz(0)!=n) return 0;
    /*vector<int> u,v,a,b;
    for(auto p:e){
        u.push_back(p.f);
        v.push_back(p.s);
        if(y[p.f]==y[p.s]){
            a.push_back((x[p.f]+x[p.s])/2);
            b.push_back(y[p.f]+1);
        }
        else{
            if(x[p.f]==2) a.push_back(1);
            else a.push_back(7);
            b.push_back((y[p.f]+y[p.s])/2);
        }
    }*/
    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