Submission #570545

#	Time	Username	Problem	Language	Result	Execution time	Memory
570545		inksamurai	IOI Fever (JOI21_fever)	C++17	37 / 100	664 ms	3028 KiB

fever

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3wX6R40 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};

signed main(){
_3wX6R40;
	int n;
	cin>>n;
	vec(pii) a(n);
	rep(i,n){
		cin>>a[i].fi>>a[i].se;
		a[i].fi*=2;
		a[i].se*=2;
	}
	assert(n<=3000);
	const int inf=8e18;
	using T=pair<int,pii>;
	int res=0;
	rep(sdir,4){
	// {
		// int sdir=0;
		priority_queue<T,vec(T),greater<T>> pq;
		vec(vi) dp(n,vi(4,inf));
		dp[0][sdir]=0;
		pq.push({0,{0,sdir}});
		while(sz(pq)){
			auto top=pq.top();
			pq.pop();
			auto [i,dir]=top.se;
			int cosu=top.fi;
			if(dp[i][dir]!=cosu) continue;
			rep(j,n){
				if(i==j) continue;
				// 0 ->
				// 1 <-
				// 2 ^
				// 3 v
				rep(ndir,4){
					if(dir==ndir) continue;
					int t=(pii)minmax(dir,ndir)==(pii){2,3}?1:(pii)minmax(dir,ndir)==(pii){0,1}?2:0;
					pii p=a[i],q=a[j];
					if(t==1){
						if(dir!=2) swap(p,q);
						if(p.se>q.se or p.fi!=q.fi) continue;
						int _t=(q.se-p.se)/2;
						if(cosu>_t) continue;
						if(dp[j][ndir]>_t){
							dp[j][ndir]=_t;
							pq.push({_t,{j,ndir}});
						}
					}else if(t==2){
						if(dir!=0) swap(p,q);
						if(p.fi>q.fi or p.se!=q.se) continue;
						int _t=(q.fi-p.fi)/2;
						if(cosu>_t) continue;
						if(dp[j][ndir]>_t){
							dp[j][ndir]=_t;
							pq.push({_t,{j,ndir}});
						}
					}else{
						if(abs(p.fi-q.fi)!=abs(p.se-q.se)) continue;
						int _t=abs(p.fi-q.fi);
						int x=p.fi+di[dir]*_t,y=p.se+dj[dir]*_t;
						int nx=q.fi+di[ndir]*_t,ny=q.se+dj[ndir]*_t;
						// print("ndir = ",ndir,", ",x,y,nx,ny,"...",p.fi,p.se,q.fi,q.se);
						if(nx!=x or ny!=y) continue;
						if(cosu>_t) continue;
						if(dp[j][ndir]>_t){
							dp[j][ndir]=_t;
							pq.push({_t,{j,ndir}});
						}
					}
				}
			}
		}
		int now=0;
		rep(i,n){
			rep(dir,4){
				now+=(dp[i][dir]<inf);
			}
		}
		res=max(res,now);
	}
	print(res);
//
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31