oj.uz

Submission #400143

# Submission time Handle Problem Language Result Execution time Memory
400143 2021-05-07T13:00:36 Z CSQ31 Park (BOI16_park) C++14
100 / 100
 423 ms 69312 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 2e6;
ll dist(ll x1,ll y1,ll x2,ll y2){
	return sqrt((x1-x2)*1LL*(x1-x2) + (y1-y2)*1LL*(y1-y2));
}
vector<pair<ll,PII>>edge;
void add(ll d,int a,int b){
	edge.pb({d,{a,b}});
}
vector<int>par(MAXN),szz(MAXN);
int find(int x){
	if(par[x] == x)return x;
	else return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a == b)return;
	if(szz[a] > szz[b])swap(a,b);
	par[a] = b;
	szz[b]+=szz[a];
}
int main()
{
	ll n,m,w,h;
	cin>>n>>m>>w>>h;
	vector<ll>x(n),y(n),r(n);
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>r[i];
		add(dist(x[i],y[i],x[i],0)-r[i],0,i+4);
		add(dist(x[i],y[i],0,y[i])-r[i],1,i+4);
		add(dist(x[i],y[i],x[i],h)-r[i],2,i+4);
		add(dist(x[i],y[i],w,y[i])-r[i],3,i+4);
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			add(dist(x[i],y[i],x[j],y[j]) - r[i] - r[j],i+4,j+4);
		}
	}
	for(int i=0;i<n+4;i++)par[i] = i;
	vector<pair<ll,pii>>q(m);
	vector<string>ans(m);
	for(int i=0;i<m;i++){
		cin>>q[i].fi>>q[i].se.fi;
		q[i].se.fi--;
		q[i].se.se = i;
	}
	sort(all(q));
	sort(all(edge));
	int ptr = 0;
	for(int i=0;i<m;i++){
		ll w = q[i].fi;
		int idx = q[i].se.se;
		int e = q[i].se.fi;
		while(ptr<sz(edge) && edge[ptr].fi < 2*w){
			unite(edge[ptr].se.fi,edge[ptr].se.se);
			ptr++;
		}
		bool c[4][4];
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)c[j][k] = (find(j) == find(k));
			
		if(e == 0){
			ans[idx]+="1";
			if(c[0][1])continue;
			if(!c[1][3] && !c[1][2])ans[idx]+='4';
			if(!c[1][3] && !c[0][2] && !c[2][3])ans[idx]+='3';
			if(!c[0][2] && !c[0][3])ans[idx]+='2';
		}
		if(e == 1){
			ans[idx]+='2';
			if(c[0][3])continue;
			if(!c[0][2] && !c[1][0])ans[idx]+='1';
			if(!c[0][2] && !c[1][3] && !c[1][2])ans[idx]+='4';
			if(!c[1][3] && !c[2][3])ans[idx]+='3';
		}
		if(e == 2){
			ans[idx]+='3';
			if(c[2][3])continue;
			if(!c[1][3] && !c[0][3])ans[idx]+='2';
			if(!c[1][3] && !c[0][2] && !c[0][1])ans[idx]+='1';
			if(!c[0][2] && !c[1][2])ans[idx]+='4';
		}
		if(e == 3){
			ans[idx]+='4';
			if(c[1][2])continue;
			if(!c[1][3] && !c[0][1])ans[idx]+='1';
			if(!c[1][3] && !c[0][2] && !c[0][3])ans[idx]+='2';
			if(!c[0][2] && !c[2][3])ans[idx]+='3';
		}
	}
	for(int i=0;i<m;i++){
		sort(all(ans[i]));
		cout<<ans[i]<<'\n';
	}
}
/*
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
* */

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 65380 KB Output is correct
2 Correct 319 ms 65276 KB Output is correct
3 Correct 300 ms 65404 KB Output is correct
4 Correct 303 ms 65352 KB Output is correct
5 Correct 297 ms 65456 KB Output is correct
6 Correct 301 ms 65428 KB Output is correct
7 Correct 291 ms 65436 KB Output is correct
8 Correct 271 ms 65432 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 8 ms 15972 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 21540 KB Output is correct
2 Correct 119 ms 22540 KB Output is correct
3 Correct 104 ms 22592 KB Output is correct
4 Correct 108 ms 22588 KB Output is correct
5 Correct 104 ms 22684 KB Output is correct
6 Correct 109 ms 22680 KB Output is correct
7 Correct 106 ms 22092 KB Output is correct
8 Correct 105 ms 22092 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 65380 KB Output is correct
2 Correct 319 ms 65276 KB Output is correct
3 Correct 300 ms 65404 KB Output is correct
4 Correct 303 ms 65352 KB Output is correct
5 Correct 297 ms 65456 KB Output is correct
6 Correct 301 ms 65428 KB Output is correct
7 Correct 291 ms 65436 KB Output is correct
8 Correct 271 ms 65432 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 8 ms 15972 KB Output is correct
11 Correct 103 ms 21540 KB Output is correct
12 Correct 119 ms 22540 KB Output is correct
13 Correct 104 ms 22592 KB Output is correct
14 Correct 108 ms 22588 KB Output is correct
15 Correct 104 ms 22684 KB Output is correct
16 Correct 109 ms 22680 KB Output is correct
17 Correct 106 ms 22092 KB Output is correct
18 Correct 105 ms 22092 KB Output is correct
19 Correct 400 ms 69120 KB Output is correct
20 Correct 394 ms 69124 KB Output is correct
21 Correct 388 ms 69240 KB Output is correct
22 Correct 397 ms 69120 KB Output is correct
23 Correct 423 ms 69076 KB Output is correct
24 Correct 373 ms 69312 KB Output is correct