oj.uz

Submission #722184

# Submission time Handle Problem Language Result Execution time Memory
722184 2023-04-11T14:00:00 Z urosk Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 340 KB 
#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 tsz = 1;
bool ok = 1;
ll root(ll x){
    while(x!=dsu[x]){
        x = dsu[x];
    }
    return x;
}
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);
    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}]){
                c.pb(i);
                d.pb(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;
    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
**/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -