제출 #408796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408796		SirCovidThe19th	Park (BOI16_park)	C++14	100 / 100	698 ms	69124 KiB

park

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

struct pt{
    long long x, y, r;
    int border; //-1, 0, 1, 2, 3 -> not border, up, right, down, left
};
struct visitor{
    int r, e, id;
};
struct edg{
    int a, b; long double w;
};

bool operator<(const edg& a, const edg& b) {
    return (a.w < b.w);
}
bool operator<(const visitor& a, const visitor& b) {
    return (a.r < b.r);
}

int n, m, w, h;
bool cn[4][4];
vector<pt> circles; vector<edg> edges; vector<visitor> people;

vector<int> par, sz; vector<vector<bool>> group;
int find(int node){
    if (par[node] == node) return node;
    return par[node] = find(par[node]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (sz[a] > sz[b]) swap(a, b);
    for (int i = 0; i < 4; i++)
        group[b][i] = (group[b][i] or group[a][i]);
    for (int i = 0; i < 4-1; i++)
        for (int j = i+1; j < 4; j++)
            if (group[b][i] and group[b][j])
                cn[i][j] = true, cn[j][i] = true;
    par[a] = b; sz[a] += b;
}

long double circleDist(pt u, pt v){
    return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y))-(u.r+v.r);
}
long double circleBorderDist(pt u, pt v){
    if (u.border == -1) swap(u, v);
    if (u.border == 0) return h-v.y-v.r;
    if (u.border == 1) return w-v.x-v.r;
    if (u.border == 2) return v.y-v.r;
    if (u.border == 3) return v.x-v.r;
}

pair<int, int> sides[4] = {{2, 3}, {2, 1}, {0, 1}, {0, 3}};
int diag[4] = {2, 3, 0, 1};
int upDown[4] = {3, 2, 1, 0}; int rightLeft[4] = {1, 0, 3, 2};
string solve(int s){
    string res = to_string(s+1); 
    if (cn[sides[s].first][sides[s].second]) 
        return res;
    if (!cn[1][3] and !cn[sides[upDown[s]].first][sides[upDown[s]].second])
        res += to_string(upDown[s]+1);
    if (!cn[0][2] and !cn[sides[rightLeft[s]].first][sides[rightLeft[s]].second])
        res += to_string(rightLeft[s]+1);
    if (!cn[0][2] and !cn[1][3] and !cn[sides[diag[s]].first][sides[diag[s]].second])
        res += to_string(diag[s]+1);
    sort(res.begin(), res.end()); return res;
}

int main(){

    cin >> n >> m >> w >> h; circles.resize(n+4); people.resize(m);
    
    for (int i = 0; i < n; i++){
        cin >> circles[i].x >> circles[i].y >> circles[i].r; 
        circles[i].border = -1;
    }
    for (int i = 0; i < 4; i++) 
        circles[i+n] = {0, 0, 0, i};
        
    for (int i = 0; i < n+4-1; i++){
        for (int j = i+1; j < n+4; j++){
            if (circles[i].border == -1 and circles[j].border == -1)
                edges.push_back({i, j, circleDist(circles[i], circles[j])});
            else if (circles[i].border == -1 or circles[j].border == -1) 
                edges.push_back({i, j, circleBorderDist(circles[i], circles[j])});
        }
    }
    
    for (int i = 0; i < m; i++){
        cin >> people[i].r >> people[i].e; 
        people[i].e--; people[i].r *= 2; people[i].id = i;
    }

    sort(edges.begin(), edges.end());
    sort(people.begin(), people.end());

    for (int i = 0; i < n+4; i++){
        sz.push_back(1); par.push_back(i);
        group.push_back(vector<bool>(4, false)); 
        if (i >= n) group[i][i-n] = true;
    }

    memset(cn, false, sizeof(cn));
    string res[m]; int pos = 0;

    for (int i = 0; i < m; i++){
        while (pos < edges.size() and edges[pos].w < people[i].r){
            merge(edges[pos].a, edges[pos].b); pos++;
        }
        res[people[i].id] = solve(people[i].e);
    }

    for (int i = 0; i < m; i++) 
        cout<<res[i]<<endl;
}

컴파일 시 표준 에러 (stderr) 메시지

park.cpp: In function 'int main()':
park.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while (pos < edges.size() and edges[pos].w < people[i].r){
      |                ~~~~^~~~~~~~~~~~~~
park.cpp: In function 'long double circleBorderDist(pt, pt)':
park.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

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