Submission #1269020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269020		cokalhado	Park (BOI16_park)	C++20	Compilation error	0 ms	0 KiB

park

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

#define int long long
#define mt make_tuple
#define is(x) c.count(x)

const int maxn = 2e3+10;
int n, m;
int w, h;
tuple<int, int, int> tr[maxn];
set<int> ans[maxn];
// 0 means it's a guy, 1 means it's a tree
vector<tuple<int, bool, int, int>> ar;
set<int> edges[maxn]; // edges connected to this guy
int pai[maxn];
int peso[maxn];

int find(int x)
{
    if(pai[x] == x) return x;
    return pai[x] = find(pai[x]);
}

void join(int a, int b)
{
    a = find(a);
    b = find(b);
    if(a == b) return;
    if(peso[a] < peso[b]) swap(a, b);
    pai[b] = a;
    peso[a] += peso[b];
    for(int i : edges[b]) edges[a].insert(i);
}

set<int> cur[5];

void rer(set<int> a)
{
    set<int> b;
    for(int i = 1; i <= 4; i++)
    {
        if(!a.count(i)) b.insert(i);
        else
        {
            // cout << "isosing " << i << " ";
        }
    }
    // cout << endl;
    for(int i : a)
    {
        for(int j : b)
        {
            cur[i].erase(j);
            cur[j].erase(i);
        }
    }
}

int main()
{
    cin >> n >> m >> w >> h;
    for(int i = 5; i <= n+4; i++)
    {
        int x, y, r;
        cin >> x >> y >> r;
        tr[i] = mt(x, y, r);
    }

    for(int i = 1; i <= m; i++)
    {
        int r, e;
        cin >> r >> e;
        ar.push_back(mt(2*r, 0, e, i)); // put the diameter to see if it'll pass
    }

    for(int i = 1; i <= 4; i++){pai[i] = i; peso[i] = 1; edges[i].insert(i);}
    for(int i = 5; i <= n+4; i++)
    {
        pai[i] = i;
        peso[i] = 1;
        auto [x, y, r] = tr[i];
        vector<pair<int, int>> wall = {{0, y}, {x, h}, {w, y}, {x, 0}};
        int c = 0;
        for(auto [j, h] : wall)
        {
            int d = abs(j-x+h-y);
            ar.push_back(mt(d-r, 1, i, ++c));
        }
        for(int j = i+1; j <= n+4; j++)
        {
            auto [x1, y1, r1] = tr[j];
            int dx = x-x1;
            int dy = y-y1;
            dx *= dx; dy *= dy;
            int dist = dx+dy;
            // send the distance in which it+1 BREAKS -> (it+1)² > dist
            dist = sqrt(dist);
            ar.push_back(mt(dist-r-r1, 1, i, j));
        }
    }

    sort(ar.begin(), ar.end());

    for(int i = 1; i < 5; i++) cur[i] = {1, 2, 3, 4}; // 1: bl, 2: br, 3: tr, 4: tl
    for(auto [size, id, i, j] : ar)
    {
        if(!id)
        {
            // put your answer according to the cur
            for(int k : cur[i])
            {
                ans[j].insert(k);
            }
        }
        else
        {
            join(i, j);
            i = pai[i];
            set<int> c = edges[i];
            set<int> a;
            a.clear();
            if(is(1) && is(3))
            {
                a.insert(4); a.insert(3);
                rer(a); a.clear();
            }
            if(is(1) && is(2))
            {
                a.insert(4);
                rer(a); a.clear();
            }
            if(is(1) && is(4))
            {
                a.insert(1);
                rer(a); a.clear();
            }
            if(is(2) && is(3))
            {
                a.insert(3);
                rer(a); a.clear();
            }
            if(is(2) && is(4))
            {
                a.insert(1); a.insert(4);
                rer(a); a.clear();
            }
            if(is(3) && is(4))
            {
                a.insert(2);
                rer(a); a.clear();
            }
        }
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j : ans[i]) cout << j;
        cout << endl;
    }
    return 0;
}

// 1: bl, 2: br, 3: tr, 4: tl
// 1: left, 2: up, 3: right, 4: down

// 1, 3 -> 4, 3 .remove(1, 2)  1, 2 .remove(3, 4)
// 1, 2 -> 4 .remove(1, 2, 3)  1, 2, 3 .remove(4)
// 1, 4 -> 1 .remove(2, 3, 4)  2, 3, 4 .remove(1)
// 2, 3 -> 3 .remove(1, 2, 4)  1, 2, 4 .remove(3)
// 2, 4 -> 1, 4 .remove(2, 3)  2, 3 .remove(1, 4)
// 3, 4 -> 2 .remove(1, 3, 4)  1, 3, 4 .remove(2)

// 5 3
// 16 11
// 11 8 1
// 6 10 1
// 7 3 2 
// 10 4 1
// 15 5 1
// 1 1
// 2 2
// 2 1

Compilation message (stderr)

cc1plus: error: '::main' must return 'int'