제출 #1171657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171657		clementine	Park (BOI16_park)	C++20	100 / 100	561 ms	55344 KiB

park

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

struct Node
{
    ll x, y, r, i;
};
struct Edge
{
    ll u, v;
    ll l;
    Edge(int uu, int vv, ll ls)
    : u(uu), v(vv), l(ls){}
};

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);

    if(x == y)
    {
        return;
    }
    if(sizee[y] > sizee[x])
    {
        swap(x, y);
    }
    parent[y] = x;
    sizee[x] += sizee[y];
}

int main()
{
    //freopen("t.in.17", "r", stdin);
    //freopen("park.out", "w", stdout);

    int n, m, w, h;
    cin >> n >> m >> w >> h;
    vector<Node> nodes;
    vector<pair<ll ,ll>> 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 = n; i <=n + 3; i ++)
    {
        Node node;
        node.r = 0;
        node.i= i;
        nodes.push_back(node);
    }
    for(int i = 0; i <m; i ++)
    {
        ll 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);
    bool connected[5][5];
    for(int i = 1; i <=4; i ++)
    {
        for(int j = 1; j <=4; j ++)
        {
            connected[i][j] = true;
        }
    }
    vector<vector<int>> ans(m, vector<int>());
    int left = 0;

    for(int j = 0; j < m; j ++)
    {
        int i = peopleidx[j];
        //cout << " person : " << people[i].first << " " << people[i].second << '\n';
        Edge e = edges[left];
        //cout << e.l << " " << pow(people[i].first * 2 + nodes[e.u].r + nodes[e.v].r, 2) << " " << people[i].first << '\n';
        while( left < edges.size() && e.l  < pow(people[i].first * 2 + nodes[e.u].r + nodes[e.v].r, 2))
        {
            //cout << " yes\n";
            unite(e.u, e.v);
            left ++;
            e = edges[left];
            //cout << e.l << " " << pow(people[i].first * 2 + nodes[e.u].r + nodes[e.v].r, 2) << " " << people[i].first << '\n';
          
        }
        //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 t = 1; t <= 4; t ++)
        {
            if(people[i].second <= t && connected[people[i].second][t])
            {
                //cout << t;
                int temp = t;
                ans[i].push_back(temp);
            }
            else
            {
                if(people[i].second > t && connected[t][people[i].second])
                {
                    //cout << t;
                    int temp = t;
                    ans[i].push_back(temp);
                }
            }
        }
        //cout <<'\n';
        //cout << " ans : " << ans[i] << '\n';
    }
    
    for(int i = 0; i < m; i ++)
    {
        for(auto val: ans[i])
            cout << val;
        cout << '\n';
    }
}

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