Submission #549907

#	Time	Username	Problem	Language	Result	Execution time	Memory
549907		AmirElarbi	Fountain Parks (IOI21_parks)	C++17	30 / 100	449 ms	62444 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18+5
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int nax2 = 105;
vii srt1[nax], srt2[nax];
ve<pair<int,ii>> ysrt[nax];
int parent[nax];
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

set<int> xs,ys;
map<ll, bool> vis;
int construct_roads(vi x, vi  y) {
    int n = x.size();
    vi u,v,a,b;
    for (int i = 0; i < n; ++i)
    {
        xs.insert(x[i]);
        ys.insert(y[i]);
        srt1[x[i]].pb({y[i], i});
        srt2[y[i]].pb({x[i], i});
        parent[i] = i;
    }
    for(auto cury : ys){
        vii srt = srt2[cury];
        sort(srt.begin(), srt.end());
        for (int i = 0; i < srt.size()-1; ++i)
        {
            int curx = srt[i].fi;
            if(srt[i+1].fi-srt[i].fi == 2)
                ysrt[curx].pb({cury,{srt[i].se,srt[i+1].se}});
        }
    }
    int cnt = 0;
    for(auto curx : xs){
        vii srt = srt1[curx];
        sort(srt.begin(), srt.end());
        for (int i = 0; i < (int)srt.size()-1; ++i)
        {
            if(srt[i+1].fi-srt[i].fi == 2){
                if(find_set(srt[i].se) == find_set(srt[i+1].se)) continue;
                u.pb(0), v.pb(0),a.pb(0),b.pb(0);
                union_sets(srt[i].se,srt[i+1].se);
                int ny = (srt[i].fi+srt[i+1].fi)/2;
                u[cnt] = srt[i].se,v[cnt] = srt[i+1].se, b[cnt] = ny;
                if(vis[ny*nax+curx-1]){
                    a[cnt] = curx+1;   
                    vis[ny*nax+curx+1] = 1;
                }
                else{
                    vis[ny*nax+curx-1] = 1;
                    a[cnt] = curx-1;  
                }
                cnt++;
            }
        }
        for(auto cury : ysrt[curx]){
            if(find_set(cury.se.fi) == find_set(cury.se.se)) continue;
            u.pb(0), v.pb(0),a.pb(0),b.pb(0);
            union_sets(cury.se.fi,cury.se.se);
            u[cnt] = cury.se.fi,v[cnt] = cury.se.se;
            a[cnt] = curx+1;
            if(!vis[(cury.fi-1)*nax+curx+1]){
                b[cnt] = cury.fi-1;   
                vis[(cury.fi-1)*nax+curx+1] = 1;
            }
            else{
                b[cnt] = cury.fi+1;   
                vis[(cury.fi+1)*nax+curx+1] = 1;
            }
            cnt++;
        }
    }
    int un = find_set(0);
    for (int i = 1; i < n; ++i)
    {
        if(find_set(i) != un) return 0;
    }
    build(u,v,a,b);
    return 1;
}

Compilation message (stderr)

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

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