Submission #1024255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024255		Abito	Fountain Parks (IOI21_parks)	C++17	5 / 100	183 ms	52688 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ep insert
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N],r[N];
vector<int> adj[N];
bool cmp(int x,int y){
    return a[x]<a[y];
}
bool cmp2(int x,int y){
    return b[x]>b[y];
}
int getpar(int x){
    if (x==par[x]) return x;
    return par[x]=getpar(par[x]);
}
void link(int x,int y){
    x=getpar(x);
    y=getpar(y);
    if (x==y) return;
    if (sz[x]>sz[y]) swap(x,y);
    sz[y]+=sz[x];
    par[x]=y;
    return;
}
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++){
        par[i]=i;
        sz[i]=1;
        a[i]=x[i];
        b[i]=y[i];
        c[y[i]].pb(i);
        r[x[i]].pb(i);
    }
    vector<int> U,V,s;
    for (int i=0;i<N;i+=2) sort(c[i].begin(),c[i].end(),cmp);
    for (int i=0;i<N;i+=2){
        for (int j=0;j<int(c[i].size())-1;j++){
            if (a[c[i][j+1]]-a[c[i][j]]==2){
                link(c[i][j],c[i][j+1]);
                U.pb(c[i][j]);
                V.pb(c[i][j+1]);
                s.pb(0);
                adj[c[i][j]].pb(U.size()-1);
                adj[c[i][j+1]].pb(U.size()-1);
            }
        }
    }
    for (int i=N-1;i>=0;i--){
        for (int j=0;j<int(c[i].size());j++){
            int l=0,r=int(c[i+2].size())-1,mid,idx=-1;
            while (l<=r){
                mid=(l+r)/2;
                if (a[c[i+2][mid]]==a[c[i][j]]){
                    idx=mid;
                    break;
                }
                if (a[c[i+2][mid]]>a[c[i][j]]) r=mid-1;
                else l=mid+1;
            }
            if (idx!=-1){
                if (getpar(c[i][j])==getpar(c[i+2][idx])) continue;
                link(c[i][j],c[i+2][idx]);
                V.pb(c[i][j]);
                U.pb(c[i+2][idx]);
                s.pb(2);
                adj[c[i][j]].pb(U.size()-1);
                adj[c[i+2][idx]].pb(U.size()-1);
            }
        }
    }
    //for (int i=0;i<U.size();i++) cout<<U[i]<<' '<<V[i]<<endl;
    if (sz[getpar(0)]!=n) return 0;
    //for (int i=0;i<N;i+=2) sort(r[i].begin(),r[i].end(),cmp2);
    vector<int> d(U.size()),e(U.size());
    set<pair<int,int>> bench;
    bool h=0;
    int last=-1;
    for (int i=0;i<U.size();i++){
        if (s[i]==0) continue;
        if (a[U[i]]!=last){
            last=a[U[i]];
            h=0;
        }
        if (!h){
            d[i]=a[U[i]]-1;
            e[i]=b[U[i]]-1;
            bench.ep({d[i],e[i]});
            h=!h;
        }
        else{
            d[i]=a[U[i]]+1;
            e[i]=b[U[i]]-1;
            bench.ep({d[i],e[i]});
            h=!h;
        }
    }
    //for (auto u:bench) cout<<u.F<<' '<<u.S<<endl;
    for (int i=0;i<U.size();i++){
        if (s[i]==2) continue;
        int xx=a[U[i]]+1,yy=b[U[i]]+1;
        if (!bench.count({xx,yy})){
            d[i]=xx;
            e[i]=yy;
            bench.ep({xx,yy});
            continue;
        }
        yy-=2;
        d[i]=xx;
        e[i]=yy;
        bench.ep({xx,yy});
    }
    build(U,V,d,e);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i=0;i<U.size();i++){
      |                  ~^~~~~~~~~
parks.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i=0;i<U.size();i++){
      |                  ~^~~~~~~~~

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