oj.uz

Submission #377947

# Submission time Handle Problem Language Result Execution time Memory
377947 2021-03-15T15:21:54 Z YJU Park (BOI16_park) C++14
100 / 100
 1189 ms 138696 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e5+10;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
const ld eps=1e-12;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
#define SQ(_a) ((_a)*(_a))

ll sz[N],dir[N];

ll find(ll nd){
	return (dir[nd]==nd?nd:dir[nd]=find(dir[nd]));
}

void Union(ll nda,ll ndb){
	nda=find(nda);ndb=find(ndb);
	if(nda==ndb)return ;
	if(sz[nda]>sz[ndb])swap(nda,ndb);
	sz[ndb]+=sz[nda];
	dir[nda]=ndb;
}

bool is(ll nda,ll ndb){
	return (find(nda)==find(ndb));
}

ll tx[N],ty[N],tr[N];
ll ans[N],qe[N],qr[N];
ll m,W,H,n;
ll side[100][20];
ll ve[40],ho[40];
vector<pair<ld,pll> > query,event;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	//prepare
	REP1(i,N-1)dir[i]=i,sz[i]=1;
	side[0][0]=n+4,side[0][1]=n+3;
	side[1][0]=n+3;side[1][1]=n+2;
	side[2][0]=n+2;side[2][1]=n+1;
	side[3][0]=n+1;side[3][1]=n+4;
	ho[0]=ho[1]=(1<<2)|(1<<3);
	ho[2]=ho[3]=(1<<1)|(1<<0);
	ve[0]=ve[3]=(1<<2)|(1<<1);
	ve[1]=ve[2]=(1<<0)|(1<<3);
	//endprepare
	cin>>W>>H;
	/*
			n+1
		-------------
		|3		   2|
	n+4	|0    	   1|n+2
		-------------
			n+3
	*/
	REP1(i,n){
		cin>>tx[i]>>ty[i]>>tr[i];
	}
	REP1(i,n)REP1(j,n){
		event.pb(mp((ld)sqrt((tx[i]-tx[j])*(tx[i]-tx[j])+(ty[i]-ty[j])*(ty[i]-ty[j]))-tr[i]-tr[j],mp(i,j)));
	}
	REP1(i,n){
		event.pb(mp(ty[i]-tr[i],mp(i,n+3)));
		event.pb(mp(H-ty[i]-tr[i],mp(i,n+1)));
		event.pb(mp(tx[i]-tr[i],mp(i,n+4)));
		event.pb(mp(W-tx[i]-tr[i],mp(i,n+2)));
	}
	REP1(i,m){
        cin>>qr[i]>>qe[i];
        query.pb(mp(2*qr[i],mp(qe[i],i)));
	}
	sort(event.begin(),event.end());
	sort(query.begin(),query.end());
	for(int i=0,j=0;i<SZ(query);i++){
        while(j<SZ(event)&&event[j].X<query[i].X){
			Union(event[j].Y.X,event[j].Y.Y);
			++j;
        }
        ll ent=query[i].Y.X-1,id=query[i].Y.Y;
        if(is(n+2,n+4)){
			ans[id]|=ho[ent];
        }
        if(is(n+1,n+3)){
			ans[id]|=ve[ent];
        }
        if(is(side[ent][0],side[ent][1])){
			ans[id]|=(((1<<4)-1)^(1<<ent));
        }
        REP(j,4){
			if(j==ent)continue;
			if(is(side[j][0],side[j][1])){
				ans[id]|=(1<<j);
			}
        }
	}
	REP1(i,m){
		REP(j,4)if(((ans[i]>>j)&1)==0)cout<<j+1;
		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 1114 ms 133460 KB Output is correct
2 Correct 1109 ms 133612 KB Output is correct
3 Correct 1123 ms 133460 KB Output is correct
4 Correct 1119 ms 133460 KB Output is correct
5 Correct 1123 ms 133460 KB Output is correct
6 Correct 1114 ms 133460 KB Output is correct
7 Correct 1104 ms 133588 KB Output is correct
8 Correct 1042 ms 133460 KB Output is correct
9 Correct 1 ms 1900 KB Output is correct
10 Correct 1 ms 1900 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9824 KB Output is correct
2 Correct 74 ms 10208 KB Output is correct
3 Correct 74 ms 10208 KB Output is correct
4 Correct 76 ms 10272 KB Output is correct
5 Correct 74 ms 10208 KB Output is correct
6 Correct 80 ms 10336 KB Output is correct
7 Correct 62 ms 9052 KB Output is correct
8 Correct 63 ms 9052 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 133460 KB Output is correct
2 Correct 1109 ms 133612 KB Output is correct
3 Correct 1123 ms 133460 KB Output is correct
4 Correct 1119 ms 133460 KB Output is correct
5 Correct 1123 ms 133460 KB Output is correct
6 Correct 1114 ms 133460 KB Output is correct
7 Correct 1104 ms 133588 KB Output is correct
8 Correct 1042 ms 133460 KB Output is correct
9 Correct 1 ms 1900 KB Output is correct
10 Correct 1 ms 1900 KB Output is correct
11 Correct 78 ms 9824 KB Output is correct
12 Correct 74 ms 10208 KB Output is correct
13 Correct 74 ms 10208 KB Output is correct
14 Correct 76 ms 10272 KB Output is correct
15 Correct 74 ms 10208 KB Output is correct
16 Correct 80 ms 10336 KB Output is correct
17 Correct 62 ms 9052 KB Output is correct
18 Correct 63 ms 9052 KB Output is correct
19 Correct 1189 ms 138696 KB Output is correct
20 Correct 1177 ms 138448 KB Output is correct
21 Correct 1178 ms 138576 KB Output is correct
22 Correct 1175 ms 138576 KB Output is correct
23 Correct 1170 ms 138448 KB Output is correct
24 Correct 1142 ms 138564 KB Output is correct