제출 #1097771

#제출 시각아이디문제언어결과실행 시간메모리
1097771HuyATPark (BOI16_park)C++17
0 / 100
425 ms94540 KiB
#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; struct circle{ int x, y; ld r; ld dist(circle a){ ld ans = (a.x - x) * (a.x - x) + (a.y - y) * (a.y - y); return sqrtl(ans); } } c[N]; bool ans[N][5]; struct bruh{ ld w; int 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; rmax = max(rmax, r); query[i] = {r * 2, e, i}; } vector<bruh> v; for(int i = 1; i <= n; ++i){ for(int j = i + 1; j <= n; ++j){ ld d = c[i].dist(c[j]); v.push_back({d - c[i].r - c[j].r, i, j}); } } int sz = v.size(); 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, r = c[i].r; if(x - r >= lx && x + r <= rx){ v.push_back({y, i, n1}); v.push_back({h - y, i, n3}); } if(y - r >= ly && y + r <= ry){ v.push_back({x, i, n4}); v.push_back({w - x, i, n2}); } } sort(all(query)); sort(all(v)); int j = 0; DSU dsu(sz); for(auto &it : query){ int r = it.w, e = it.u, id = it.v; while(j < sz && v[j].w < (ld)(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:73:23: warning: narrowing conversion of '(r * 2)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
   73 |         query[i] = {r * 2, e, i};
      |                     ~~^~~
park.cpp:89:26: warning: narrowing conversion of 'y' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
   89 |             v.push_back({y, i, n1});
      |                          ^
park.cpp:90:28: warning: narrowing conversion of '(h - y)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
   90 |             v.push_back({h - y, i, n3});
      |                          ~~^~~
park.cpp:93:26: warning: narrowing conversion of 'x' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
   93 |             v.push_back({x, i, n4});
      |                          ^
park.cpp:94:28: warning: narrowing conversion of '(w - x)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
   94 |             v.push_back({w - x, i, n2});
      |                          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...