Could someone help me with BOI Park?

Problems and Contests
#1

Hi,

I have been trying to implement the solution to https://oj.uz/problem/view/BOI16_park which is in the DSU category for usaco.guide. I’ve been doing the solution described in the usaco.guide editorial written here https://usaco.guide/solutions/baltic-16-park
My implementation gets one case on subtask 1 and one case on subtask 3 but ultimately gets 0/100. Here is my code: https://hastebin.com/zusopoyuze.cpp
In my code I assigned the borders n(top), n+1(right), n+2(bottom), and n+3(left). If anybody could tell me what I’m doing wrong or maybe just give me a better way to implement it that would be nice.
Thanks!

#2

As an alternative to creating four extra nodes to represent the borders, you can instead store, for each component, whether it “touches” each of the four borders. I think this makes the implementation easier. Here’s my implementation which follows this approach (note that my implementation is pretty awful…) https://github.com/thecodingwizard/competitive-programming/blob/master/BOI/Baltic%2016-park.cpp

Additionally, I would highly recommend getting full score on the first subtask before trying to attempt the other two :slight_smile:

#3

How would you know if the borders are connected? Would you store for each border the component it is in?

Also, how would you recommend prioritizing getting full score on the first subtask? Should I make a different solution all together to solve the first subtask. I did manage to get another test case on subtasks 1 and 3 by

#define int long long
#4

Yeah, I would store it for each component.

bool wallTop[maxn], wallBot[maxn], wallLeft[maxn], wallRight[maxn];

There might be a neater way than with four boolean arrays… I was really lazy and just used those four arrays along with the following (insanely dumb) code:

bool can[4][4];

void updCan(int i) {
    //cout << i << endl;
    if (wallTop[i] && wallBot[i]) {
        //cout << "top & bot" << endl;
        can[0][1] = can[0][2] = can[3][1] = can[3][2] = can[1][0] = can[2][0] = can[1][3] = can[2][3] = 0;
    }
    if (wallTop[i] && wallLeft[i]) {
        //cout << "top & left" << endl;
        can[3][0] = can[3][1] = can[3][2] = can[0][3] = can[1][3] = can[2][3] = 0;
    }
    if (wallTop[i] && wallRight[i]) {
        //cout << "top & right" << endl;
        can[2][0] = can[2][1] = can[2][3] = can[0][2] = can[1][2] = can[3][2] = 0;
    }
    if (wallLeft[i] && wallRight[i]) {
        //cout << "left & right" << endl;
        can[2][0] = can[2][1] = can[0][2] = can[1][2] = can[0][3] = can[1][3] = can[3][1] = can[3][0] = 0;
    }
    if (wallLeft[i] && wallBot[i]) {
        //cout << "left & bot" << endl;
        can[0][3] = can[0][1] = can[0][2] = can[2][0] = can[1][0] = can[3][0] = 0;
    }
    if (wallRight[i] && wallBot[i]) {
        //cout << "right & bot" << endl;
        can[1][0] = can[1][3] = can[1][2] = can[0][1] = can[3][1] = can[2][1] = 0;
    }
}