제출 #1097817

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097817		HuyAT	Park (BOI16_park)	C++17	27 / 100	203 ms	51900 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};

struct DSU{
    vi par, sz;
    int n;
    DSU(int _n){
        n = _n;
        sz.assign(n + 1, 1);
        par.assign(n + 1, 0);
        iota(all(par), 0);
    }
    int root(int u){
        if(par[u] == u) return u;
        return par[u] = root(par[u]);
    }
    bool same(int u, int v){
        return root(u) == root(v);
    }
    void unite(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
    }
};

const int N = 2010;
const int NN = 1e5 + 5;

struct circle{
    int x, y, r;
    int dist(circle a){
        ld ans = (a.x - x) * (a.x - x) + (a.y - y) * (a.y - y);
        return sqrtl(ans);
    }
} c[N];

bool ans[NN][5];

struct bruh{
    int w, u, v;
    bool operator < (bruh &a) const {
        return w < a.w;
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    int w, h; cin >> w >> h;
    for(int i = 1; i <= n; ++i) cin >> c[i].x >> c[i].y >> c[i].r;
    vector<bruh> query(m);
    int rmax = 0;
    FOR(i, m){
        int e, r; cin >> r >> e;
        r *= 2;
        rmax = max(rmax, r);
        query[i] = {r, e, i};
    }
    vector<bruh> v;
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            int d = c[i].dist(c[j]);
            v.push_back({d - c[i].r - c[j].r, i, j});
        }
    }
    int sz = n;
    int n1 = sz + 1, n2 = sz + 2, n3 = sz + 3, n4 = sz + 4;
    sz += 4;
    int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
    for(int i = 1; i <= n; ++i){
        int x = c[i].x, y = c[i].y; ld r = c[i].r;
        if(x - r >= lx && x + r <= rx){
            v.push_back({y - r, i, n1});
            v.push_back({h - y - r, i, n3});
        }
        if(y - r >= ly && y + r <= ry){
            v.push_back({x - r, i, n4});
            v.push_back({w - x - r, i, n2});
        }
    }
    sort(all(query));
    sort(all(v));
    int j = 0, lim = v.size();
    DSU dsu(sz);
    for(auto &it : query){
        int r = it.w, e = it.u, id = it.v;
        while(j < lim && v[j].w < r){
            int U = v[j].u, V = v[j].v;
            dsu.unite(U, V);
            ++j;
        }
        for(int i = 1; i <= 4; ++i){
            if(i == e)
                continue;
            if(e == 1){
                if(dsu.same(n1, n4)) ans[id][i] = 1;
                if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n2));
                if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n2, n3));
                if(i == 4) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n3, n4));
            }
            if(e == 2){
                if(dsu.same(n1, n2)) ans[id][i] = 1;
                if(i == 3) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n2, n3));
                if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n3, n4));
                if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n4));
            }
            if(e == 3){
                if(dsu.same(n2, n3)) ans[id][i] = 1;
                if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n3, n4));
                if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n4));
                if(i == 2) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n2));
            }
            if(e == 4){
                if(dsu.same(n3, n4)) ans[id][i] = 1;
                if(i == 1) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n4));
                if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n2));
                if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n3));
            }
        }
    }
    FOR(i, m){
        for(int j = 1; j <= 4; ++j) if(!ans[i][j]) cout << j;
        cout << "\n";
    }
    return 0;
}

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

park.cpp: In function 'int main()':
park.cpp:90:28: warning: narrowing conversion of '((ld)y - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   90 |             v.push_back({y - r, i, n1});
      |                          ~~^~~
park.cpp:91:32: warning: narrowing conversion of '((ld)(h - y) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   91 |             v.push_back({h - y - r, i, n3});
      |                          ~~~~~~^~~
park.cpp:94:28: warning: narrowing conversion of '((ld)x - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   94 |             v.push_back({x - r, i, n4});
      |                          ~~^~~
park.cpp:95:32: warning: narrowing conversion of '((ld)(w - x) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   95 |             v.push_back({w - x - r, i, n2});
      |                          ~~~~~~^~~

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