Submission #722186

#	Time	Username	Problem	Language	Result	Execution time	Memory
722186		urosk	Fountain Parks (IOI21_parks)	C++17	25 / 100	1250 ms	83888 KiB

parks

#include "parks.h"
#define here cerr<<"==============================\n"
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
#define maxn 200005
ll n;
pll a[maxn];
map<pll,ll> mp;
map<pll,ll> id;
vector<ll> dx = {0,0,-2,2};
vector<ll> dy = {-2,2,0,0};
ll sz[maxn];
ll dsu[maxn];
ll col[maxn];
ll dsu2[maxn];
ll root2(ll x){
    while(x!=dsu2[x]){
        dsu2[x] = dsu2[dsu2[x]];
        x = dsu2[x];
    }
    return x;
}
bool con(ll x,ll y){return root2(x)==root2(y);}
ll tsz = 1;
bool ok = 1;
ll root(ll x){
    while(x!=dsu[x]){
        x = dsu[x];
    }
    return x;
}
void upd2(ll i,ll j){
    i = root2(i);
    j = root2(j);
    dsu2[j] = dsu2[i];
}
ll getcol(ll x){
    ll ans = col[x];
    while(x!=dsu[x]){
        x = dsu[x];
        ans^=col[x];
    }
    return ans;
}
void upd(ll i,ll j,ll e){
    e^=getcol(i)^getcol(j);
    i = root(i);
    j = root(j);
    if(i==j){
        if(e) ok = 0;
        return;
    }
    if(sz[j]>sz[i]) swap(i,j);
    sz[i]+=sz[j];
    dsu[j] = i;
    col[j]^=e;
}
int construct_roads(vector<int> X, vector<int> Y) {
    n = X.size();
    for(ll i = 1;i<=n;i++) a[i] = {X[i-1],Y[i-1]};
    for(ll i = 1;i<=n;i++) mp[a[i]] = i;
    iota(dsu+1,dsu+1+n,1);
    iota(dsu2+1,dsu2+1+n,1);
    fill(sz+1,sz+1+n,1);
    vector<ll> c,d;
    for(ll i = 1;i<=n;i++){
        ll x = a[i].fi,y = a[i].sc;
        vector<ll> v;
        for(ll e = 0;e<=3;e++){
            ll nx = x + dx[e];
            ll ny = y + dy[e];
            ll j = mp[{nx,ny}];
            v.pb(j);
            if(j&&!id[{i,j}]&&!con(i,j)){
                c.pb(i);
                d.pb(j);
                upd2(i,j);
                id[{i,j}] = id[{j,i}] = ++tsz;
            }
        }
        if(v[1]&&v[3]) upd(id[{i,v[1]}],id[{i,v[3]}],1);
        if(v[0]&&v[2]) upd(id[{i,v[0]}],id[{i,v[2]}],1);
        if(v[1]&&v[2]) upd(id[{i,v[1]}],id[{i,v[2]}],0);
        if(v[0]&&v[3]) upd(id[{i,v[0]}],id[{i,v[3]}],0);
    }
    if(!ok) return 0;
    if(c.size()<n-1) return 0;
    vector<pll> ans;
    for(ll i = 0;i<n-1;i++){
        ll x = c[i];
        ll y = d[i];
        ll j = id[{x,y}];
        ll f = getcol(j);
        if(a[x].fi==a[y].fi){
            if(f) ans.pb({a[x].fi+1,(a[x].sc+a[y].sc)/2});
            else ans.pb({a[x].fi-1,(a[x].sc+a[y].sc)/2});
        }else{
            if(f) ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc+1});
            else ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc-1});
        }
    }
    vector<ll> ansx,ansy;
    for(pll p : ans){
        ansx.pb(p.fi);
        ansy.pb(p.sc);
    }
    for(ll i = 0;i<n-1;i++){
        c[i]--;
        d[i]--;
    }
    build(c,d,ansx,ansy);
    return 1;
}
/**
5
4 4
4 6
6 4
4 2
2 4
**/

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:92:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     if(c.size()<n-1) return 0;
      |        ~~~~~~~~^~~~

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