제출 #723913

#제출 시각아이디문제언어결과실행 시간메모리
723913nicky4321Park (BOI16_park)C++17
100 / 100
2344 ms162004 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define F first #define S second #define PB push_back #define MP make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> #define ALL(x) x.begin(), x.end() #define vi vector<int> #define vl vector<ll> #define SZ(x) (int)x.size() #define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++) #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int MAX = 1 << 20, MOD = 1e9 + 7; ll x[MAX], y[MAX], r[MAX], ptr[MAX], num[MAX]; vector<pair<ll, pii> > qq; string ans[MAX]; int find(int x){ return x != ptr[x] ? ptr[x] = find(ptr[x]) : x; } void uf(int u, int v){ u = find(u); v = find(v); if(u == v) return; if(num[u] > num[v]) swap(u, v); num[v] += num[u]; ptr[u] = v; return; } void solve(){ int n, q; cin >> n >> q; ll w, h; cin >> w >> h; for(int i = 1;i <= n;i++){ cin >> x[i] >> y[i] >> r[i]; } for(int i = 1;i <= q;i++){ ll rr, ty; cin >> rr >> ty; qq.PB(MP(rr, MP(ty, i))); } sort(ALL(qq)); for(int i = 1;i <= n + 4;i++){ ptr[i] = i; num[i] = 1; } set<pair<ll, pii> > st; for(int i = 1;i <= n;i++){ for(int j = i + 1;j <= n;j++){ ll tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); st.insert(MP(ceil(sqrt(tmp)) - r[i] - r[j] + (ceil(sqrt(tmp)) * ceil(sqrt(tmp)) == tmp), MP(i, j))); } } for(int i = 1;i <= n;i++){ st.insert(MP(x[i] - r[i] + 1, MP(i, n + 1))); st.insert(MP(h - y[i] - r[i] + 1, MP(i, n + 2))); st.insert(MP(w - x[i] - r[i] + 1, MP(i, n + 3))); st.insert(MP(y[i] - r[i] + 1, MP(i, n + 4))); } for(int i = 0;i < q;i++){ ll rr = qq[i].F, ty = qq[i].S.F, id = qq[i].S.S; while(!st.empty() && (*st.begin()).F <= rr * 2){ uf((*st.begin()).S.F, (*st.begin()).S.S); st.erase(st.begin()); } if(ty == 1){ ans[id] += "1"; if(find(n + 4) != find(n + 1) && find(n + 4) != find(n + 2) && find(n + 4) != find(n + 3)) ans[id] += "2"; if(find(n + 2) != find(n + 4) && find(n + 2) != find(n + 3) && find(n + 1) != find(n + 4) && find(n + 1) != find(n + 3)) ans[id] += "3"; if(find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3) && find(n + 1) != find(n + 4)) ans[id] += "4"; }else if(ty == 2){ if(find(n + 4) != find(n + 1) && find(n + 4) != find(n + 2) && find(n + 4) != find(n + 3)) ans[id] += "1"; ans[id] += "2"; if(find(n + 3) != find(n + 1) && find(n + 3) != find(n + 2) && find(n + 3) != find(n + 4)) ans[id] += "3"; if(find(n + 2) != find(n + 4) && find(n + 3) != find(n + 4) && find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3)) ans[id] += "4"; }else if(ty == 3){ if(find(n + 2) != find(n + 4) && find(n + 2) != find(n + 3) && find(n + 1) != find(n + 4) && find(n + 1) != find(n + 3)) ans[id] += "1"; if(find(n + 3) != find(n + 1) && find(n + 3) != find(n + 2) && find(n + 3) != find(n + 4)) ans[id] += "2"; ans[id] += "3"; if(find(n + 2) != find(n + 1) && find(n + 2) != find(n + 3) && find(n + 2) != find(n + 4)) ans[id] += "4"; }else{ if(find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3) && find(n + 1) != find(n + 4)) ans[id] += "1"; if(find(n + 2) != find(n + 4) && find(n + 3) != find(n + 4) && find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3)) ans[id] += "2"; if(find(n + 2) != find(n + 1) && find(n + 2) != find(n + 3) && find(n + 2) != find(n + 4)) ans[id] += "3"; ans[id] += "4"; } } for(int i = 1;i <= q;i++) cout << ans[i] << '\n'; } /* 2 1 3 4 */ int main(){ IOS // CASE solve(); return 0; } /* 5 3 16 11 11 8 1 6 10 1 7 3 2 10 4 1 15 5 1 1 1 2 2 2 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...