Submission #1171596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171596		clementine	Park (BOI16_park)	C++20	27 / 100	579 ms	33552 KiB

park

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

struct Node
{
    ll x, y, r, i;
};
struct Edge
{
    int u, v;
    ll l;
    Edge(int uu, int vv, ll ls)
    : u(uu), v(vv), l(ls){}
};
// { distance ^2, second node }
//vector<pair<int, int>> graph[2010];
int parent[2010];
int sizee[2010];

void build(int n)
{
    for(int i = 0;i <=n; i ++)
    {
        parent[i]= i;
        sizee[i] = 1;
    }
}

int find(int a)
{
    if(parent[a] ==a) return a;
    parent[a] = find(parent[a]);
    return parent[a];
}

void unite(int x, int y)
{
    x= find(x);
    y = find(y);
    //cout << " d " << x << " abd "<< y << "\n";
    if(x == y)
    {
        return;
    }
    if(sizee[y] > sizee[x])
    {
        swap(x, y);
    }
    parent[y] = x;
    sizee[x] += sizee[y];
}

int main()
{
    int n, m, w, h;
    cin >> n >> m >> w >> h;
    vector<Node> nodes;
    vector<pair<ll ,int>> people;
    vector<int> peopleidx;
    for(int i = 0; i <n; i ++)
    {
        Node node;
        cin >> node.x >> node.y >> node.r; 
        node.i = i;
        nodes.push_back(node);
    }
    for(int i = 1; i <=m; i ++)
    {
        int r, e;
        cin>> r >> e;
        people.push_back({r, e});
        peopleidx.push_back(i);
    }
    sort(peopleidx.begin(), peopleidx.end(), [&](int a, int b){return people[a].first < people[b].first;});
    vector<Edge> edges;
    for(int i = 1; i <n; i ++)
    {
        for(int j = 0; j < i; j ++)
        {
            // distance^2 without minusing radii
            ll dist = abs(nodes[i].x - nodes[j].x)* abs(nodes[i].x - nodes[j].x);
            dist += abs(nodes[i].y - nodes[j].y) * abs(nodes[i].y - nodes[j].y);
            Edge e(i, j, dist);
            edges.push_back(e);
            //graph[i].push_back({dist, j});
            //graph[j].push_back({dist, i});
        }
    }
    // treat the edges of the park as other nodes
    for(int i = 0; i < n; i ++)
    {
        Edge e(n, i, pow(nodes[i].y, 2));
        edges.push_back(e);
        //cout << " \n heres an edge added :" <<e.u <<" " <<  e.v << "  " << nodes[i].y << " " << pow(nodes[i].y, 2) << " " << e.l << '\n';
        Edge e1(n + 1, i, pow(w - nodes[i].x, 2));
        edges.push_back(e1);
        //cout << e.u <<" " <<  e.v << "  " << nodes[i].y << " " << pow(nodes[i].y, 2)<< '\n';
        Edge e2(n + 2, i, pow(h - nodes[i].y, 2));
        edges.push_back(e2);
        //cout << e2.u <<" " <<  e2.v << "  " << nodes[i].y << " " << pow(nodes[i].y, 2)<< '\n';
        Edge e3(n + 3, i , pow(nodes[i].x, 2));
        edges.push_back(e3); 
        //cout << e.u <<" " <<  e.v << "  " << nodes[i].y << " " << pow(nodes[i].y, 2)<< '\n';
    }
    sort(edges.begin(), edges.end(), [&](Edge a, Edge b)
        {
            return sqrt(a.l) - nodes[a.u].r - nodes[a.v].r < sqrt(b.l) - nodes[b.u].r - nodes[b.v].r;
        });
    /*
    for(int i = 0; i < edges.size(); i ++)
    {
        Edge e = edges[i];
        cout << "edge i: \n";
        cout << " u : " << e.u << " v : " << e.v  << " l : " << e.l << " u's radius : " << nodes[e.u].r << " v's radius : " << nodes[e.v].r << '\n';
    }*/
    build(n + 3);
    for(auto e: edges)
    {
        //cout << " uniting : " << e.u << " " << e.v << " " << e.l << " " << pow(people[0].first + nodes[e.u].r + nodes[e.v].r, 2) << "\n";
        if(e.l  < pow(people[0].first * 2 + nodes[e.u].r + nodes[e.v].r, 2))
        {
            //cout << " yes\n";
            unite(e.u, e.v);
        }
    }
    bool connected[5][5];
    for(int i = 1; i <=4; i ++)
    {
        for(int j = 1; j <=4; j ++)
        {
            connected[i][j] = true;
        }
    }
    //cout << " blocked :\n";
    if(find(n) == find(n + 1))
    {
        //cout << n << " " << n + 1 << '\n';
        connected[1][2] = connected[2][3] = connected[2][4] = false;
    }
    if(find(n + 1) == find(n + 2))
    {
        //cout << n+ 1 << " " << n + 2 << '\n';
        connected[1][3] = connected[2][3] = connected[3][4] = false;
    }
    if(find(n + 2) == find(n+ 3))
    {
        //cout << n +2 << " " << n + 3 << '\n';
        connected[1][4] = connected[2][4] = connected[3][4] = false;
    }
    if(find(n + 3) == find(n))
    {
        //cout << n+3 << " " << n << '\n';
        connected[1][2] = connected[1][3] = connected[1][4] = false;
    }
    if(find(n) == find(n + 2))
    {
        //cout << n << " " << n + 2 << '\n';
        connected[1][2] = connected[1][3] = connected[2][4] = connected[3][4] = false;
    }
    if(find(n +1) == find(n + 3))
    {
        //cout << n+3 << " " << n + 1 << '\n';
        connected[1][3] = connected[1][4] = connected[2][3] = connected[2][4] = false;
    }
    for(int i = 1; i <= 4; i ++)
    {
        if(people[0].second <= i && connected[people[0].second][i])
        {
            cout << i;
        }
        else
        {
            if(people[0].second > i && connected[i][people[0].second])
            {
                cout << i;
            }
        }
    }
    /*
    for(int i = 0; i <m; i ++)
    {

    }*/

}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42