Submission #1231949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231949		a4n_	Fountain Parks (IOI21_parks)	C++20	0 / 100	470 ms	57920 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 4e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, x[N], y[N], used[N], x2[N], y2[N], dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1}, par[N], mark[N];
map<pii, int> mp;
// vector<pii> vecx[N];
vector<int> adj[N], ansu, ansv, ansa, ansb;

int getPar(int v) {return (par[v] == 0 ? v : par[v] = getPar(par[v])); }

void merge(int v, int u, int wh) {
    v = getPar(v), u = getPar(u);
    if(v == u) return;
    par[v] = u;
    ansv.pb(v - 1);
    ansu.pb(u - 1);
    ansa.pb(x2[wh]);
    ansb.pb(y2[wh]);
    used[wh] = 1;
}

void dfs(int v) {
    mark[v] = 1;
    for(int u : adj[v]) {
        if(used[v] == 0) {
            int tx = (x2[v] + x2[u]) / 2, ty = (y2[v] + y2[u]) / 2;
            if(tx%2 == 1) {
                // cout<<x2[v]<<' '<<y2[v]<<" ==> "<<tx-1<<" "<<ty<<"   ~   "<<tx+1<<" "<<ty<<endl;
                merge(mp[{tx-1, ty}], mp[{tx+1, ty}], v);    
            } else {
                // cout<<x2[v]<<' '<<y2[v]<<" ==> "<<tx<<" "<<ty-1<<"   ~   "<<tx<<" "<<ty+1<<endl;
                merge(mp[{tx, ty-1}], mp[{tx, ty+1}], v);
            }
        }
        if(mark[u] == 1) continue;
        dfs(u);
    }
}

int construct_roads(vector<int> _x, vector<int> _y) {
    n = size(_x);
    for(int i=1; i<=n; i++) x[i] = _x[i-1], y[i] = _y[i-1], mp[{x[i], y[i]}] = i;

    int cnt = 1;
    map<pii, int> id;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<4; j++) {
            int tx = x[i] + dx[j], ty = y[i] + dy[j];
            if(mp[{tx+dx[j], ty+dy[j]}] == 0) continue;
            
            if(tx%2 == 1) {
                int s1, s2;
                
                if(id[{tx, ty-1}] == 0) x2[cnt]=tx, y2[cnt]=ty-1, id[{tx, ty-1}] = cnt++;
                if(id[{tx, ty+1}] == 0) x2[cnt]=tx, y2[cnt]=ty+1, id[{tx, ty+1}] = cnt++;
                
                s1 = id[{tx, ty-1}], s2 = id[{tx, ty+1}];
                adj[s1].pb(s2);
                adj[s2].pb(s1);
            } else {
                int s1, s2;
                
                if(id[{tx-1, ty}] == 0) x2[cnt]=tx-1, y2[cnt]=ty, id[{tx-1, ty}] = cnt++;
                if(id[{tx+1, ty}] == 0) x2[cnt]=tx+1, y2[cnt]=ty, id[{tx+1, ty}] = cnt++;
                
                s1 = id[{tx-1, ty}], s2 = id[{tx+1, ty}];
                adj[s1].pb(s2);
                adj[s2].pb(s1);
            }
        }
    }

    for(int i=1; i<cnt; i++) if(size(adj[i]) == 1 && mark[i] == 0) dfs(i);
    for(int i=1; i<cnt; i++) if(mark[i] == 0) dfs(i);


    for(int i=1; i<=n; i++) {
        if(getPar(i) != getPar(1)) return 0; 
    }
    build(ansu, ansv, ansa, ansb);
    return 1;
}

// void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

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