Submission #396431

#	Time	Username	Problem	Language	Result	Execution time	Memory
396431		arnold518	IOI Fever (JOI21_fever)	C++17	100 / 100	869 ms	42184 KiB

fever

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const int INF = 2147483647;

struct Point
{
	int x, y, p;
};

int N;
Point A[MAXN+10];

struct Queue
{
	int u, d; int w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

int dist[MAXN+10];

int d(int u, int v)
{
	return (abs(A[u].x-A[v].x)+abs(A[u].y-A[v].y));
}

int ans;

unordered_map<int, vector<int>> M1, M2, M3, M4;

bool cmpx(int p, int q)
{
	return A[p].x<A[q].x;
}

bool cmpy(int p, int q)
{
	return A[p].y<A[q].y;
}

int norm(int x)
{
	x%=N;
	if(x==0) x=N;
	return x;
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].x, &A[i].y);
		A[i].x*=2; A[i].y*=2;
		A[i].p=i;
	}

	for(int i=1; i<=N; i++)
	{
		M1[A[i].x-A[i].y].push_back(i);
		M2[A[i].x+A[i].y].push_back(i);
		M3[A[i].x].push_back(i);
		M4[A[i].y].push_back(i);
	}

	for(auto &it : M1)
	{
		sort(it.second.begin(), it.second.end(), cmpx);
	}

	for(auto &it : M2)
	{
		sort(it.second.begin(), it.second.end(), cmpy);
	}

	for(auto &it : M3)
	{
		sort(it.second.begin(), it.second.end(), cmpy);
	}

	for(auto &it : M4)
	{
		sort(it.second.begin(), it.second.end(), cmpx);
	}

	priority_queue<Queue> PQ;
	for(int p=0; p<4; p++)
	{
		for(int i=1; i<=N*9; i++) dist[i]=INF;

		PQ.push({1, p, 0});
		while(!PQ.empty())
		{
			Queue now=PQ.top(); PQ.pop();
			if(dist[now.u]<=now.w) continue;
			dist[now.u]=now.w;
			//printf("%d %d : %d\n", now.u, now.d, now.w);

			int u=norm(now.u);
			auto &V1=M1[A[u].x-A[u].y];
			auto &V2=M2[A[u].x+A[u].y];
			auto &V3=M3[A[u].x];
			auto &V4=M4[A[u].y];

			if(now.u<=N)
			{
				if(now.d==0)
				{
					{
						A[0].x=A[now.u].x+now.w/2;
						auto it=upper_bound(V1.begin(), V1.end(), 0, cmpx);
						if(it!=V1.end())
						{
							PQ.push({*it+N*1, 3, d(now.u, *it)});
						}
					}
					{
						A[0].y=A[now.u].y+now.w/2;
						auto it=upper_bound(V2.begin(), V2.end(), 0, cmpy);
						if(it!=V2.end())
						{
							PQ.push({*it+N*2, 1, d(now.u, *it)});
						}
					}
					{
						A[0].y=A[now.u].y+now.w;
						auto it=upper_bound(V3.begin(), V3.end(), 0, cmpy);
						if(it!=V3.end())
						{
							PQ.push({*it+N*3, 2, d(now.u, *it)});
						}
					}
				}
				if(now.d==3)
				{
					{
						A[0].y=A[now.u].y+now.w/2;
						auto it=upper_bound(V2.begin(), V2.end(), 0, cmpy);
						if(it!=V2.end())
						{
							PQ.push({*it+N*2, 2, d(now.u, *it)});
						}
					}
					{
						A[0].x=A[now.u].x-now.w/2;
						auto it=lower_bound(V1.begin(), V1.end(), 0, cmpx);
						if(it!=V1.begin())
						{
							it--;
							PQ.push({*it+N*5, 0, d(now.u, *it)});
						}
					}
					{
						A[0].x=A[now.u].x-now.w;
						auto it=lower_bound(V4.begin(), V4.end(), 0, cmpx);
						if(it!=V4.begin())
						{
							it--;
							PQ.push({*it+N*8, 1, d(now.u, *it)});
						}
					}
				}
				if(now.d==2)
				{
					{
						A[0].x=A[now.u].x-now.w/2;
						auto it=lower_bound(V1.begin(), V1.end(), 0, cmpx);
						if(it!=V1.begin())
						{
							it--;
							PQ.push({*it+N*5, 1, d(now.u, *it)});
						}
					}
					{
						A[0].y=A[now.u].y-now.w/2;
						auto it=lower_bound(V2.begin(), V2.end(), 0, cmpy);
						if(it!=V2.begin())
						{
							it--;
							PQ.push({*it+N*6, 3, d(now.u, *it)});
						}
					}
					{
						A[0].y=A[now.u].y-now.w;
						auto it=lower_bound(V3.begin(), V3.end(), 0, cmpy);
						if(it!=V3.begin())
						{
							it--;
							PQ.push({*it+N*7, 0, d(now.u, *it)});
						}
					}
				}
				if(now.d==1)
				{
					{
						A[0].y=A[now.u].y-now.w/2;
						auto it=lower_bound(V2.begin(), V2.end(), 0, cmpy);
						if(it!=V2.begin())
						{
							it--;
							PQ.push({*it+N*6, 0, d(now.u, *it)});
						}
					}
					{
						A[0].x=A[now.u].x+now.w/2;
						auto it=upper_bound(V1.begin(), V1.end(), 0, cmpx);
						if(it!=V1.end())
						{
							PQ.push({*it+N*1, 2, d(now.u, *it)});
						}
					}
					{
						A[0].x=A[now.u].x+now.w;
						auto it=upper_bound(V4.begin(), V4.end(), 0, cmpx);
						if(it!=V4.end())
						{
							PQ.push({*it+N*4, 3, d(now.u, *it)});
						}
					}
				}
			}
			else if(now.u<=N*2)
			{

				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V1.begin(), V1.end(), u, cmpx);
				it++;
				if(it!=V1.end())
				{
					PQ.push({*it+N, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*3)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V2.begin(), V2.end(), u, cmpy);
				it++;
				if(it!=V2.end())
				{
					PQ.push({*it+N*2, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*4)
			{
				//printf("%d %d %d\n", u, now.d, now.w);
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V3.begin(), V3.end(), u, cmpy);
				it++;
				if(it!=V3.end())
				{
					PQ.push({*it+N*3, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*5)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V4.begin(), V4.end(), u, cmpx);
				it++;
				if(it!=V4.end())
				{
					PQ.push({*it+N*4, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*6)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V1.begin(), V1.end(), u, cmpx);
				if(it!=V1.begin())
				{
					it--;
					PQ.push({*it+N*5, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*7)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V2.begin(), V2.end(), u, cmpy);
				if(it!=V2.begin())
				{
					it--;
					PQ.push({*it+N*6, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*8)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V3.begin(), V3.end(), u, cmpy);
				if(it!=V3.begin())
				{
					it--;
					PQ.push({*it+N*7, now.d, now.w+d(u, *it)});
				}
			}
			else if(now.u<=N*9)
			{
				PQ.push({u, now.d, now.w});
				auto it=lower_bound(V4.begin(), V4.end(), u, cmpx);
				if(it!=V4.begin())
				{
					it--;
					PQ.push({*it+N*8, now.d, now.w+d(u, *it)});
				}
			}
		}
		int cnt=0;
		for(int i=1; i<=N; i++)
		{
			if(dist[i]!=INF) cnt++;
			//printf("%d ", dist[i]);
		}
		//printf("%d\n", cnt);
		ans=max(ans, cnt);
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
fever.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d", &A[i].x, &A[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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