Submission #1050636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050636		Malix	Fountain Parks (IOI21_parks)	C++17	30 / 100	1361 ms	89260 KiB

parks

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

map<pi,pi> p;
map<pi,int> s,num,used;

pi parent(pi x){
    if(p[x]==x)return x;
    return p[x]=parent(p[x]);
}

void join(pi x,pi y){
    x=parent(x);
    y=parent(y);
    if(x==y)return;
    if(s[x]<s[y])swap(x,y);
    s[x]+=s[y];
    p[y]=x;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n=x.size();
    int mx=0;
    REP(i,0,n)mx=max(mx,x[i]);
if(mx==2){
    pii a;
    REP(i,0,n)a.PB({y[i],i});
    sort(a.begin(),a.end());
    vii ans(4);
    REP(i,0,n-1){
        if(a[i].F+2!=a[i+1].F)return 0;
        ans[0].PB(a[i].S);
        ans[1].PB(a[i+1].S);
        ans[2].PB(3);
        ans[3].PB(a[i].F+1);
    }
    build(ans[0],ans[1],ans[2],ans[3]);
    return 1;
}
if(mx==4){
    REP(i,0,n)s[{x[i],y[i]}]=1;
    REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
    REP(i,0,n)num[{x[i],y[i]}]=i;
    vii ans(4);
    REP(i,2,5){
        REP(j,2,200001){
            if(j<200000&&s[{i,j}]>0&&s[{i,j+2}]>0){
                join({i,j},{i,j+2});
                ans[0].PB(num[{i,j}]);
                ans[1].PB(num[{i,j+2}]);
                if(i==2)ans[2].PB(i-1);
                else ans[2].PB(i+1);
                ans[3].PB(j+1);
            }
            if(i==2&&s[{i,j}]>0&&s[{i+2,j}]>0){
                join({i,j},{i+2,j});
                ans[0].PB(num[{i,j}]);
                ans[1].PB(num[{i+2,j}]);
                ans[2].PB(i+1);
                ans[3].PB(j-1);
            }
            j++;
        }
        i++;
    }
    pi t=parent({x[0],y[0]});
    bool flag=1;
    REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
    if(flag){
        build(ans[0],ans[1],ans[2],ans[3]);
        return 1;
    }
    return 0;
}
if(mx==6){
    REP(i,0,n)s[{x[i],y[i]}]=1;
    REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
    REP(i,0,n)num[{x[i],y[i]}]=i;
    vii ans(4);
    REP(i,2,7){
        REP(j,2,200000){
            if(s[{i,j}]>0&&s[{i,j+2}]>0){
                join({i,j},{i,j+2});
                ans[0].PB(num[{i,j}]);
                ans[1].PB(num[{i,j+2}]);
                if(i==2)ans[2].PB(i-1);
                else if(i==6)ans[2].PB(i+1);
                else if(i==4){
                    if((j/2)%2==0)ans[2].PB(i+1);
                    else ans[2].PB(i-1);
                }
                ans[3].PB(j+1);
                used[{ans[2].back(),ans[3].back()}]=1;
            }
            j++;
        }
        i++;
    }
    REP(i,2,5){
        REP(j,2,200001){
            if(s[{i,j}]>0&&s[{i+2,j}]>0&&parent({i,j})!=parent({i+2,j})){
                if(used[{i+1,j-1}]==1&&used[{i+1,j+1}])return 0;
                join({i,j},{i+2,j});
                ans[0].PB(num[{i,j}]);
                ans[1].PB(num[{i+2,j}]);
                if(used[{i+1,j-1}]==1){
                    ans[2].PB(i+1);
                    ans[3].PB(j+1);
                }
                else{
                    ans[2].PB(i+1);
                    ans[3].PB(j-1);
                }
            }
            j++;
        }
        i++;
    }
    pi t=parent({x[0],y[0]});
    bool flag=1;
    REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
    if(flag){
        build(ans[0],ans[1],ans[2],ans[3]);
        return 1;
    }
    return 0;
}
    REP(i,0,n)s[{x[i],y[i]}]=1;
    REP(i,0,n)p[{x[i],y[i]}]={x[i],y[i]};
    REP(i,0,n)num[{x[i],y[i]}]=i;
    vii ans(4);
    pii loc={{0,2},{0,-2},{2,0},{-2,0}};
    REP(i,0,n){
        REP(j,0,4)if(s[{x[i]+loc[j].F,y[i]+loc[j].S}]>0&&parent({x[i],y[i]})!=parent({x[i]+loc[j].F,y[i]+loc[j].S})){
            join({x[i],y[i]},{x[i]+loc[j].F,y[i]+loc[j].S});
            ans[0].PB(num[{x[i],y[i]}]);
            ans[1].PB(num[{x[i]+loc[j].F,y[i]+loc[j].S}]);
            if(loc[j].F==0){
                if(used[{x[i]-1,min(y[i],y[i]+loc[j].S)+1}]==1&&used[{x[i]+1,min(y[i],y[i]+loc[j].S)+1}]==1)return 0;
                if(used[{x[i]-1,min(y[i],y[i]+loc[j].S)+1}]==1){
                    used[{x[i]+1,min(y[i],y[i]+loc[j].S)+1}]=1;
                    ans[2].PB(x[i]+1);
                    ans[3].PB(min(y[i],y[i]+loc[j].S)+1);
                }
                else{
                    used[{x[i]-1,min(y[i],y[i]+loc[j].S)+1}]=1;
                    ans[2].PB(x[i]-1);
                    ans[3].PB(min(y[i],y[i]+loc[j].S)+1);
                }
            }
            else{
                if(used[{min(x[i],x[i]+loc[j].F)+1,y[i]-1}]==1&&used[{min(x[i],x[i]+loc[j].F)+1,y[i]+1}]==1)return 0;
                if(used[{min(x[i],x[i]+loc[j].F)+1,y[i]-1}]==1){
                    used[{min(x[i],x[i]+loc[j].F)+1,y[i]+1}]=1;
                    ans[2].PB(min(x[i],x[i]+loc[j].F)+1);
                    ans[3].PB(y[i]+1);
                }
                else{
                    used[{min(x[i],x[i]+loc[j].F)+1,y[i]-1}]=1;
                    ans[2].PB(min(x[i],x[i]+loc[j].F)+1);
                    ans[3].PB(y[i]-1);
                }
            }
        }
    }
    pi t=parent({x[0],y[0]});
    bool flag=1;
    REP(i,0,n)if(parent({x[i],y[i]})!=t)flag=0;
    if(flag){
        build(ans[0],ans[1],ans[2],ans[3]);
        return 1;
    }
    return 0;
}

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