Submission #385781

#TimeUsernameProblemLanguageResultExecution timeMemory
385781erfanmirPark (BOI16_park)C++11
27 / 100
525 ms70908 KiB
// In the name of god #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define all(x) (x).begin(),(x).end() #define lc(x) (x) << 1 #define rc(x) (x) << 1 | 1 #define F first #define S second #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout); #define mp make_pair ll poww(ll a, ll b, ll md) { ll ans = 1; for(; b; b >>= 1, a = a * a % md){ if(b & 1){ ans = ans * a % md; } } return ans % md; } const int MAXN = 3e3 + 10; const int MAXLG = 18; const int MOD = 1e9 + 7; const int MOD2 = 998244353; const ll INF = 8e18; const ld ep = 1e-12; int n, m, w, h; int par[MAXN], sz[MAXN]; ll x[MAXN], y[MAXN], r[MAXN]; int ans[4][4]; vector<int> res[200010]; vector<pair<ld, pii> > edge; vector<pair<pair<ld, ll>, int> > q; int getroot(int v){ if(par[v] == v){ return v; } return par[v] = getroot(par[v]); } void merg(int v, int u){ v = getroot(v); u = getroot(u); if(v == u){ return; } if(sz[v] < sz[u]){ swap(v, u); } par[u] = v; sz[v] += sz[u]; } void preprocess(){ int st[4]; for(int i = 0; i < 4; i++){ st[i] = getroot(n + i); } ans[0][1] = (st[0] != st[1]) && (st[1] != st[2]) && (st[1] != st[3]); ans[1][2] = (st[1] != st[2]) && (st[2] != st[3]) && (st[2] != st[0]); ans[2][3] = (st[2] != st[3]) && (st[3] != st[0]) && (st[3] != st[1]); ans[0][2] = (st[0] != st[1]) && (st[2] != st[3]) && (st[0] != st[2]) && (st[1] != st[3]); ans[1][3] = (st[0] != st[3]) && (st[2] != st[1]) && (st[0] != st[2]) && (st[1] != st[3]); ans[0][3] = (st[3] != st[0]) && (st[0] != st[1]) && (st[0] != st[2]); for(int i = 0; i < 4; i++){ for(int j = 0; j < 4; j++){ if(i == j){ ans[i][j] = 1; } if(i > j){ ans[i][j] = ans[j][i]; } } } } int main() { scanf("%d %d %d %d", &n, &m, &w, &h); for(int i = 0; i < n; i++){ scanf("%lld %lld %lld\n", x + i, y + i, r + i); ld tmp = x[i] - r[i]; edge.push_back(mp(tmp, mp(i, n))); tmp = w - x[i] - r[i]; edge.push_back(mp(tmp, mp(i, n + 2))); tmp = y[i] - r[i]; edge.push_back(mp(tmp, mp(i, n + 1))); tmp = h - y[i] - r[i]; edge.push_back(mp(tmp, mp(i, n + 3))); for(int j = 0; j < i; j++){ tmp = sqrt((ld)abs(x[i] - x[j]) * abs(x[i] - x[j]) + (ld)abs(y[i] - y[j]) * abs(y[i] - y[j])) - (ld)r[i] - (ld)r[j]; edge.push_back(mp(tmp, mp(j, i))); } } for(int i = 0; i < m; i++){ ll a, b; scanf("%lld %lld", &a, &b); a *= 2; b--; q.push_back(mp(mp((ld)a, b), i)); } sort(all(edge)); sort(all(q)); for(int i = 0; i < n + 4; i++){ par[i] = i; sz[i] = 1; } int cnt = 0; for(int i = 0; i < m; i++){ while(cnt < (int)edge.size() && ep < q[i].F.F - edge[cnt].F){ merg(edge[cnt].S.F, edge[cnt].S.S); preprocess(); cnt++; } for(int j = 0; j < 4; j++){ if(ans[q[i].F.S][j]){ res[q[i].S].push_back(j + 1); } } } for(int i = 0; i < m; i++){ for(auto u : res[i]){ printf("%d", u); } printf("\n"); } }

Compilation message (stderr)

park.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
park.cpp: In function 'int main()':
park.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d %d %d", &n, &m, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         scanf("%lld %lld %lld\n", x + i, y + i, r + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |         scanf("%lld %lld", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...