oj.uz

Submission #525160

# Submission time Handle Problem Language Result Execution time Memory
525160 2022-02-10T22:43:15 Z codr0 Park (BOI16_park) C++14
100 / 100
 2478 ms 34020 KB 
// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
typedef pair<int,int> pii;
const int N=2e3+10;
vector<int> adj[N];
int dis[5][5],n,h,w;
bool mark[N];
vector<pair<pii,int>> cy;

	void dfs(int v){
		mark[v]=1;
		for(int u:adj[v]) if(!mark[u]) dfs(u);
	}

	void FILL_adj(int X){
		FOR(i,0,N-1) adj[i].clear();
		FOR(i,0,n-1) FOR(j,0,n-1) if(i!=j){
			int X1=cy[i].F.F;
			int Y1=cy[i].F.S;
			int R1=cy[i].S;
			int X2=cy[j].F.F;
			int Y2=cy[j].F.S;
			int R2=cy[j].S;
			long long dis=(abs(X1-X2)*abs(X1-X2))+(abs(Y1-Y2)*abs(Y1-Y2));
			long long go=(R1+R2+2*X)*(R1+R2+2*X);
			if(go>dis){
				adj[i+5].pb(j+5);
			}
		}
		FOR(i,0,n-1){
			int XX=cy[i].F.F;
			int YY=cy[i].F.S;
			int R=cy[i].S;
			if(XX-2*X-R<0){
				adj[i+5].pb(4);
				adj[4].pb(i+5);
			}
			if(XX+2*X+R>h){
				adj[i+5].pb(2);
				adj[2].pb(i+5);
			}
			if(YY-2*X-R<0){
				adj[i+5].pb(1);
				adj[1].pb(i+5);
			}
			if(YY+2*X+R>w){
				adj[i+5].pb(3);
				adj[3].pb(i+5);
			}
		}
	}

	void pre(){
		FOR(i,1,4) dis[i][i]=2e9;
		FOR(i,1,4) FOR(j,i+1,4){
			//dis[i][j] & dis[j][i]
			int l=-1,r=2e9;
			while(r-l>1){
				int mid=(r+l)/2;
				FOR(wz,0,N-1) mark[wz]=0;
				FILL_adj(mid);
				dfs(i);
				if(mark[j]) r=mid;
				else l=mid;
			}
			dis[i][j]=dis[j][i]=r;
		}
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int m;
	cin>>n>>m>>h>>w;
	FOR(i,1,n){
		int x,y,r; cin>>x>>y>>r;
		cy.pb({{x,y},r});
	}
	pre();
	FOR(i,1,m){
		int r,e; cin>>r>>e;
		bool ans[5]; FOR(i,1,4) ans[i]=1;
		FOR(i,1,4) FOR(j,i+1,4) if(dis[i][j]<=r){
			if(j==i+3){
				if(e!=1) ans[1]=0;
				else{
					ans[3]=ans[2]=ans[4]=0;
				}
			}
			if(j==(i+1)){
				if(e!=j) ans[j]=0;
				else{
					FOR(w,1,4) if(w!=j) ans[w]=0;
				}
			}
			if(j==(i+2)){
				if(i==2){
					if(e<3){
						ans[3]=ans[4]=0;
					}else{
						ans[1]=ans[2]=0;
					}
				}else{
					if(e==2||e==3){
						ans[1]=ans[4]=0;
					}else{
						ans[2]=ans[3]=0;
					}
				}
			}
		}
		FOR(i,1,4) if(ans[i]) cout<<i;
		cout<<'\n';
	}

	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
*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1758 ms 32680 KB Output is correct
2 Correct 1815 ms 32676 KB Output is correct
3 Correct 1778 ms 32676 KB Output is correct
4 Correct 1727 ms 32676 KB Output is correct
5 Correct 1706 ms 32708 KB Output is correct
6 Correct 1723 ms 32676 KB Output is correct
7 Correct 2466 ms 32708 KB Output is correct
8 Correct 2368 ms 32684 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2164 KB Output is correct
2 Correct 49 ms 2148 KB Output is correct
3 Correct 47 ms 2116 KB Output is correct
4 Correct 47 ms 2176 KB Output is correct
5 Correct 47 ms 2244 KB Output is correct
6 Correct 71 ms 2184 KB Output is correct
7 Correct 27 ms 1800 KB Output is correct
8 Correct 28 ms 1744 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1758 ms 32680 KB Output is correct
2 Correct 1815 ms 32676 KB Output is correct
3 Correct 1778 ms 32676 KB Output is correct
4 Correct 1727 ms 32676 KB Output is correct
5 Correct 1706 ms 32708 KB Output is correct
6 Correct 1723 ms 32676 KB Output is correct
7 Correct 2466 ms 32708 KB Output is correct
8 Correct 2368 ms 32684 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 48 ms 2164 KB Output is correct
12 Correct 49 ms 2148 KB Output is correct
13 Correct 47 ms 2116 KB Output is correct
14 Correct 47 ms 2176 KB Output is correct
15 Correct 47 ms 2244 KB Output is correct
16 Correct 71 ms 2184 KB Output is correct
17 Correct 27 ms 1800 KB Output is correct
18 Correct 28 ms 1744 KB Output is correct
19 Correct 1774 ms 34020 KB Output is correct
20 Correct 1788 ms 33884 KB Output is correct
21 Correct 1765 ms 34012 KB Output is correct
22 Correct 1813 ms 33992 KB Output is correct
23 Correct 1742 ms 33880 KB Output is correct
24 Correct 2478 ms 34016 KB Output is correct