Submission #1024254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024254		Abito	Fountain Parks (IOI21_parks)	C++17	15 / 100	114 ms	35744 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N];
vector<int> adj[N];
bool cmp(int x,int y){
    return a[x]<a[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);
    }
    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);
            }
        }
    }
    if (sz[getpar(0)]!=n) return 0;
    for (int i=0;i<U.size();i++){
        if (s[i]!=2) continue;
        int l=2,r=2,idxl=-1,idxr=-1;
        for (auto u:adj[V[i]]){
            int to=U[u];
            if (to==V[i]) to=V[u];
            if (a[to]==a[V[i]]) continue;
            if (a[to]>a[V[i]] && s[u]==0) r=0,idxr=u;
            if (a[to]<a[V[i]] && s[u]==0) l=0,idxl=u;
        }
        //cout<<l<<' '<<r<<endl;
        for (auto u:adj[U[i]]){
            int to=U[u];
            if (to==U[i]) to=V[u];
            if (a[to]==a[U[i]]) continue;
            if (a[to]>a[U[i]] && s[u]==1) r=1,idxr=u;
            if (a[to]<a[U[i]] && s[u]==1) l=1,idxl=u;
        }
        //cout<<U[i]<<' '<<V[i]<<' '<<l<<' '<<r<<' '<<idxl<<' '<<idxr<<endl;
        if (l==2 || r==2){
            //cout<<"c1"<<endl;
            if (r==2) s[i]=3;
            continue;
        }
        if (l==1){
            s[idxr]=1;
            s[i]=3;
            //cout<<"c2"<<endl;
            continue;
        }
        if (r==1){
            //cout<<"c3"<<endl;
            s[idxl]=1;
            continue;
        }
        //cout<<"c4"<<endl;
        s[idxl]=1;
    }
    vector<int> d,e;
    for (int i=0;i<U.size();i++){
        if (s[i]==0){
            d.pb(a[U[i]]+1);
            e.pb(b[U[i]]+1);
            continue;
        }
        if (s[i]==1){
            d.pb(a[U[i]]+1);
            e.pb(b[U[i]]-1);
            continue;
        }
        if (s[i]==2){
            d.pb(a[U[i]]-1);
            e.pb(b[U[i]]-1);
            continue;
        }
        d.pb(a[U[i]]+1);
        e.pb(b[U[i]]-1);
        continue;
    }
    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:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i=0;i<U.size();i++){
      |                  ~^~~~~~~~~
parks.cpp:115:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i=0;i<U.size();i++){
      |                  ~^~~~~~~~~

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