Submission #1201372

#TimeUsernameProblemLanguageResultExecution timeMemory
1201372goulthenPark (BOI16_park)C++20
100 / 100
681 ms69084 KiB
//#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define rep(i, a, b) for (int i = a; i <= b; ++i) #define per(i, b, a) for (int i = b; i >= a; --i) #define pb push_back #define eb emplace_back #define all(v) (v).begin(), (v).end() #define lsb(x) (x)&(-x) void setIO(string name = "") { ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); if (!name.empty()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } ll fexp(ll a, ll b, ll m) { if (b == 0) return 1LL; ll p = a; ll ans = 1; while (b > 0) { if (b % 2 != 0) ans = (ans*p)%m; p = (p*p)%m; b >>= 1; } return ans; } const int MAXN = 2e3+10; const long long INF = 1e18+5; const int MOD = 1e9+7; int rp[MAXN],sz_[MAXN]; int find(int x) { if (x==rp[x]) return x; return rp[x] = find(rp[x]); } void join(int x,int y) { x = find(x); y = find(y); if (x==y) return; if (sz_[x] > sz_[y]) swap(x,y); rp[x] = y; sz_[y] += sz_[x]; } void solve() { int n,m,w,h;cin >> n >> m >> w >> h; //n(+1: bottom, +2: left, +3: right, +4: top) vector<array<int,4>> a; vector<array<int,4>> dist; rep(i,1,n) { int x,y,r;cin >> x >> y >> r; dist.pb({i,n+1,y*y,r}); dist.pb({i,n+2,x*x,r}); dist.pb({i,n+3,(w-x)*(w-x),r}); dist.pb({i,n+4,(h-y)*(h-y),r}); for (const auto &[cx,cy,cr,ci] : a) { int cd = (x-cx)*(x-cx)+(y-cy)*(y-cy); dist.pb({i,ci,cd,cr+r}); } a.pb({x,y,r,i}); } vector<array<int,3>> q; vector<int> szs; rep(i,1,m) { int o,sz;cin >> sz >> o; q.pb({sz,o,i}); szs.pb(sz); } int mn[5][5]; sort(all(szs)); rep(dii,1,4) { rep(djj,dii+1,4) { mn[dii][djj] = INF; int lo = 1, hi = m; while (lo <= hi){ int mid = (lo + hi)/2; int rc = szs[mid-1]; rep(i,1,n+4) { rp[i] = i; sz_[i] = 1; } //cout << rc << '\n'; for (const auto &[x,y,d,rs] : dist) { if (d < (2*rc+rs)*(2*rc+rs)) { //can he pass if they touch //cout << x << ' ' << y << '\n'; join(x,y); } } //cout << find(n+1)<< ' ' << find(n+2) << ' ' << find(n+3) << ' ' << find(n+4) << '\n'; if (find(n+dii) == find(n+djj)) { mn[dii][djj] = rc; hi = mid-1; }else { lo = mid +1; } } } } //n(+1: bottom, +2: left, +3: right, +4: top) //cout << mn[1][4] << ' ' <<mn[1][3] << ' ' << mn[1][4] <<'\n'; for (const auto &[sz,o,i] : q) { string ans = ""; if (o==1) { ans.pb('1'); if (mn[1][3]>sz && mn[1][2]>sz && mn[1][4]>sz) ans.pb('2'); if (mn[1][2]>sz && mn[3][4]>sz && mn[2][3]>sz && mn[1][4]>sz) ans.pb('3'); if (mn[1][2]>sz && mn[2][3]>sz && mn[2][4]>sz) ans.pb('4'); } if (o==2) { if (mn[1][3]>sz && mn[1][2]>sz && mn[1][4]>sz) ans.pb('1'); ans.pb('2'); if (mn[1][3]>sz && mn[3][4]>sz && mn[2][3]>sz) ans.pb('3'); if (mn[1][3]>sz && mn[2][4]>sz && mn[2][3]>sz && mn[1][4]>sz) ans.pb('4'); } if (o==3) { if (mn[1][2]>sz && mn[3][4]>sz && mn[2][3]>sz && mn[1][4]>sz) ans.pb('1'); if (mn[1][3]>sz && mn[3][4]>sz && mn[2][3]>sz) ans.pb('2'); ans.pb('3'); if (mn[1][4]>sz && mn[2][4]>sz && mn[3][4]>sz) ans.pb('4'); } if (o==4) { if (mn[1][2]>sz && mn[2][3]>sz && mn[2][4]>sz) ans.pb('1'); if (mn[1][3]>sz && mn[2][4]>sz && mn[2][3]>sz && mn[1][4]>sz) ans.pb('2'); if (mn[1][4]>sz && mn[2][4]>sz && mn[3][4]>sz) ans.pb('3'); ans.pb('4'); } cout << ans << '\n'; } } int32_t main() { setIO(); int tt = 1; //cin >> tt; while (tt-- > 0) solve(); }

Compilation message (stderr)

park.cpp: In function 'void setIO(std::string)':
park.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...