Submission #953178

#	Time	Username	Problem	Language	Result	Execution time	Memory
953178		WonderfulWhale	IOI Fever (JOI21_fever)	C++17	25 / 100	5057 ms	14308 KiB

fever

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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

ostream& operator<<(ostream &os, pair<auto, auto> x) {
	os << "{" << x.st << ", " << x.nd << "}";
	return os;
}

const int MAXN = 100'009;

pii tab[MAXN];
int dis[MAXN];
int dir[MAXN];
vector<int> G[MAXN][4];
int n;

int f(int a, int b) {
	return abs(tab[a].st-tab[b].st)+abs(tab[a].nd-tab[b].nd);
}

int dijkstra(int s, int s_dir) {
	fill(dis, dis+n, 2e9);
	fill(dir, dir+n, -1);
	int cnt = 0;
	dis[s] = 0;
	dir[s] = s_dir;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({dis[s], s});
	while(sz(Q)) {
		auto [d_x, x] = Q.top();
		Q.pop();
		if(d_x!=dis[x]) continue;
		cnt++;
		// cerr << "dij: " << tab[x] << " " << d_x << "\n";
		for(int y:G[x][dir[x]]) {
			// cerr << "one: " << tab[y] << "\n";
			int d = f(x, y);
			if(d<d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				int ndir = (dir[x]+1)%4;
				assert(dir[y]==-1||dir[y]==ndir);
				dir[y] = ndir;
				Q.push({dis[y], y});
			}
		}
		for(int y:G[x][(dir[x]+1)%4]) {
			// cerr << "two: " << tab[y] << "\n";
			int d = f(x, y);
			// cout << tab[x] << " " << tab[y] << " " << d << "\n";
			if(d<d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				int ndir = dir[x]-1;
				if(ndir<0) ndir+=4;
				assert(dir[y]==-1||dir[y]==ndir);
				dir[y] = ndir;
				Q.push({dis[y], y});
			}
		}
	}
	return cnt;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	int ANS = 0;
	for(int i=0;i<n;i++) {
		int a, b;
		cin >> a >> b;
		// tab[i] = {a, b};
		tab[i] = {a+b, a-b};
		if(a==b) ANS++;
		// cerr << i << ": " << tab[i] << "\n";
	}
	for(int i=0;i<n;i++) {
		auto [a1, b1] = tab[i];
		// if(i==0) cerr << "TU: " << tab[i] << "\n";
		for(int j=0;j<n;j++) {
			auto [a2, b2] = tab[j];
			if(a1<a2&&b1==b2) {
				// if(i==0) cerr << "0: " << tab[j] << "\n";
				G[i][0].pb(j);
			}
			if(a1==a2&&b2>b1) {
				// if(i==0) cerr << "1: " << tab[j] << "\n";
				G[i][1].pb(j);
			}
			if(a1>a2&&b1==b2) {
				// if(i==0) cerr << "2: " << tab[j] << "\n";
				G[i][2].pb(j);
			}
			if(a1==a2&&b2<b1) {
				// if(i==0) cerr << "3: " << tab[j] << "\n";
				G[i][3].pb(j);
			}
		}
	}
	int ans = 0;
	// ans = dijkstra(0, 0);
	for(int i=0;i<4;i++) {
		ans = max(ans, dijkstra(0, i));
	}
	// cout << ans << "\n";
	cout << ans << "\n";
}

Compilation message (stderr)

fever.cpp:12:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                       ^~~~
fever.cpp:12:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                             ^~~~

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