제출 #1099963

#제출 시각아이디문제언어결과실행 시간메모리
1099963InvMODPark (BOI16_park)C++14
0 / 100
64 ms28100 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define gcd __gcd #define vsz(v) (int) v.size() #define pb push_back #define pi pair<int,int> #define all(v) (v).begin(), (v).end() #define compact(v) (v).erase(unique(all(v)), (v).end()) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) ///#define int long long using ll = long long; using ld = long double; using ull = unsigned long long; template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;} template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;} const int N = 1e5+5; const ll MOD = 1e9+7; const ll INF = 1e18; struct Circle{ int x,y,r; Circle(int x = 0, int y = 0, int r = 0): x(x), y(y), r(r) {} }; struct Edge{ int u,v,w; Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {} bool operator < (const Edge& q) const{ return w < q.w; } }; struct Query{ int id, entrance, r; Query(int id = 0, int entrance = 0, int r = 0): id(id), entrance(entrance), r(r) {} bool operator < (const Query &q) const{ return r < q.r; } }; struct DSU{ vector<int> par,sz; DSU(int n = 0): par(n+1), sz(n+1) { for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; } return; } int asc(int x){ return x == par[x] ? x : par[x] = asc(par[x]); } bool join(int u, int v){ u = asc(u), v = asc(v); if(u == v) return false; if(sz[u] < sz[v]) swap(u, v); par[v] = u; sz[u] += sz[v]; return true; } bool in(int u, int v){ return asc(u) == asc(v); } }; int n, q, h, w, answer[N]; vector<Edge> E; Circle a[N]; Query Q[N]; ll square(int x){ return (1ll * x * x); } int calc_dist(Circle a, Circle b){ return 1ll * square(a.x - b.x) + 1ll * square(a.y - b.y) + square(a.r + b.r) - 2 * sqrt(1ll * square(a.x - b.x) + 1ll * square(a.y - b.y)) * (a.r + b.r); } int f(int x){ return n+x; } void solve() { cin >> n >> q >> w >> h; for(int i = 1; i <= n; i++){ int x,y,r; cin >> x >> y >> r; a[i] = Circle(x, y, r); } for(int i = 1; i <= n; i++){ for(int j = i+1; j <= n; j++){ E.push_back(Edge(i, j, calc_dist(a[i], a[j]))); } } for(int i = 1; i <= q; i++){ int entrance,r; cin >> r >> entrance; Q[i] = Query(i, entrance, square((r<<1))); } for(int i = 1; i <= n; i++){ E.push_back(Edge(i, f(1), calc_dist(a[i], Circle(0, a[i].y)))); E.push_back(Edge(i, f(2), calc_dist(a[i], Circle(a[i].x, h)))); E.push_back(Edge(i, f(3), calc_dist(a[i], Circle(w, a[i].y)))); E.push_back(Edge(i, f(4), calc_dist(a[i], Circle(a[i].x, 0)))); } sort(all(E)); sort(Q+1, Q+1+q); DSU dsu(f(4)); int curE = 0; for(int i = 1; i <= q; i++){ while(curE < E.size() && E[curE].w < Q[i].r){ int u = E[curE].u, v = E[curE].v; dsu.join(u, v); curE = curE + 1; } /* for(int x = 1; x <= 4; x++){ for(int y = x+1; y <= 4; y++){ if(dsu.in(f(x), f(y))){ cout << x <<" " << y <<"\n"; } } } cout <<"\n"; */ int id = Q[i].id, cur_en = Q[i].entrance; //check bit = 1 if can't visit that entrance int check = 0; if(cur_en == 1){ //Check die if(dsu.in(f(1), f(4))){ for(int j = 1; j <= 4; j++){ if(cur_en != j){ check = check | (1<<j); } } } else{ //Check horizontal if(dsu.in(f(1), f(3))){ check = check | (1<<3); check = check | (1<<4); } //Check vertical if(dsu.in(f(2), f(4))){ check = check | (1<<3); check = check | (1<<2); } //Check virtual if(dsu.in(f(1), f(2))){ check = check | (1<<4); } if(dsu.in(f(4), f(3))){ check = check | (1<<2); } if(dsu.in(f(3), f(2))){ check = check | (1<<3); } } } else if(cur_en == 2){ //Check die if(dsu.in(f(3), f(4))){ for(int j = 1; j <= 4; j++){ if(cur_en != j){ check = check | (1<<j); } } } else{ //Check horizontal if(dsu.in(f(1), f(3))){ check = check | (1<<3); check = check | (1<<4); } //Check vertical if(dsu.in(f(2), f(4))){ check = check | (1<<1); check = check | (1<<4); } //Check virtual if(dsu.in(f(1), f(4))){ check = check | (1<<1); } if(dsu.in(f(1), f(2))){ check = check | (1<<4); } if(dsu.in(f(3), f(2))){ check = check | (1<<3); } } } else if(cur_en == 3){ //Check die if(dsu.in(f(2), f(3))){ for(int j = 1; j <= 4; j++){ if(cur_en != j){ check = check | (1<<j); } } } else{ //Check horizontal if(dsu.in(f(1), f(3))){ check = check | (1<<1); check = check | (1<<2); } //Check vertical if(dsu.in(f(2), f(4))){ check = check | (1<<1); check = check | (1<<4); } //Check virtual if(dsu.in(f(1), f(4))){ check = check | (1<<1); } if(dsu.in(f(4), f(3))){ check = check | (1<<2); } if(dsu.in(f(1), f(2))){ check = check | (1<<4); } } } else if(cur_en == 4){ //Check die if(dsu.in(f(1), f(2))){ for(int j = 1; j <= 4; j++){ if(cur_en != j){ check = check | (1<<j); } } } else{ //Check horizontal if(dsu.in(f(1), f(3))){ check = check | (1<<1); check = check | (1<<2); } //Check vertical if(dsu.in(f(2), f(4))){ check = check | (1<<3); check = check | (1<<2); } //Check virtual if(dsu.in(f(1), f(4))){ check = check | (1<<1); } if(dsu.in(f(4), f(3))){ check = check | (1<<2); } if(dsu.in(f(3), f(2))){ check = check | (1<<3); } } } answer[id] = check; } for(int i = 1; i <= q; i++){ for(int j = 1; j <= 4; j++){ if(answer[i]>>j&1) continue; else{ cout << j; } } cout <<"\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "InvMOD" if(fopen(name".INP", "r")){ freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout); } int t = 1; //cin >> t; while(t--) solve(); return 0; }

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

park.cpp: In function 'void solve()':
park.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         while(curE < E.size() && E[curE].w < Q[i].r){
      |               ~~~~~^~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:298:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  298 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:299:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  299 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...