Submission #1219049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219049		brinton	Fountain Parks (IOI21_parks)	C++20	55 / 100	1002 ms	60600 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

int construct_roads(vector<int> x, vector<int> y) {
    int N = x.size();
    map<pair<int,int>,int> mp;
    for(int i = 0;i < N;i++) mp[{x[i],y[i]}] = i;
    vector<int> vis(N,false);

    int dx[4] = {0,2,-2,0};
    int dy[4] = {2,0,0,-2};
    vector<int> u,v,a,b;

    set<pair<int,int>> banned;
    function<bool(int,int)> add_road = [&](int aidx,int bidx){
        int midx = (x[aidx]+x[bidx])/2;
        int midy = (y[aidx]+y[bidx])/2;
        if(x[aidx] == x[bidx]){
            // vertical
            if((midy/2)%2 == (midx/2)%2){
                midx++;
            }else{
                midx--;
            }
        }else{
            // horizontal
            if((midx/2)%2 == (midy/2)%2){
                midy--;
            }else{
                midy++;
            }
        }

        if(banned.count({midx,midy})) return false;
        banned.insert({midx,midy});
        {
            int nidx1 = -1,nidx2 = -1;
            for(int d = 0;d < 4;d++){
                int nx = midx+dx[d]/2;
                int ny = midy+dy[d]/2;
                if(nx == x[aidx] && ny == y[aidx]) continue;
                if(nx == x[bidx] && ny == y[bidx]) continue;
                if(mp.count({nx,ny})){
                    if(nidx1 == -1) nidx1 = mp[{nx,ny}];
                    else nidx2 = mp[{nx,ny}];
                }
            }
            if(nidx1 != -1 && nidx2 != -1){
                vis[nidx1] = true;
                vis[nidx2] = true;
                if(x[aidx] == x[nidx1] || y[aidx] == y[nidx1]){
                    add_road(aidx,nidx1);
                    add_road(bidx,nidx2);
                }else{
                    add_road(aidx,nidx2);
                    add_road(bidx,nidx1);
                }
            }
        }

        u.push_back(aidx);
        v.push_back(bidx);
        a.push_back(midx);
        b.push_back(midy);
        return true;
    };
    function<void(int)> dfs = [&](int idx){
        // cout << "!" << idx << endl;
        vis[idx] = true;
        int cx = x[idx],cy = y[idx];
        for(int d = 0;d < 4;d++){
            int nx = cx+dx[d];
            int ny = cy+dy[d];
            if(!mp.count({nx,ny})) continue;
            int nidx = mp[{nx,ny}];
            if(vis[nidx]) continue;
            if(add_road(idx,nidx)) dfs(nidx);
        }
    };
    dfs(0);
    for(int i = 1;i < N;i++){
        if(vis[i]) dfs(i);// check if filled by square
    }
    for(auto &i:vis){
        if(!i) return 0;
    }
    build(u,v,a,b);
    return true;
}

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