oj.uz

Submission #953065

# Submission time Handle Problem Language Result Execution time Memory
953065 2024-03-25T11:43:43 Z WonderfulWhale IOI Fever (JOI21_fever) C++17
6 / 100
 3 ms 13144 KB 
#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;

namespace B1 {

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

int dijkstra(int x, int x_dir) {
	fill(dis, dis+n, 1e9);
	int cnt = 0;
	dis[x] = 0;
	dir[x] = x_dir;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({dis[x], x});
	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;
				dir[y] = (dir[x]+1)%4;
				Q.push({dis[y], y});
			}
		}
		for(int y:G[x][(dir[x]+1)%4]) {
			// cerr << "two: " << 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;
				if(ndir<0) ndir+=4;
				dir[y] = ndir;
				Q.push({dis[y], y});
			}
		}
	}
	return cnt;
}
}
 
namespace B2 {
int f(int a, int b) {
	return tab[a].st-tab[b].st+tab[a].nd-tab[b].nd;
}
 
int dijkstra(int x, int x_dir) {
	fill(dis, dis+n, 1e9);
	int cnt = 0;
	dis[x] = 0;
	dir[x] = x_dir;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({dis[x], x});
	while(sz(Q)) {
		auto [d_x, x] = Q.top();
		Q.pop();
		if(d_x!=dis[x]) continue;
		cnt++;
		for(int y:G[x][dir[x]]) {
			int d = f(x, y);
			if(d>d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				dir[y] = (dir[x]+1)%4;
				Q.push({dis[y], y});
			}
		}
		for(int y:G[x][(dir[x]+1)%4]) {
			int d = f(x, y);
			if(d>d_x) continue;
			if(d<dis[y]) {
				dis[y] = d;
				int ndir = dir[x]-1;
				if(ndir<0) ndir+=4;
				dir[y] = ndir;
				Q.push({dis[y], y});
			}
		}
	}
	return cnt;
}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i=0;i<n;i++) {
		int a, b;
		cin >> a >> b;
		tab[i] = {a+b, a-b};
		// 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 ans1 = 0;
	// ans = dijkstra(0, 0);
	for(int i=0;i<4;i++) {
		ans1 = max(ans1, B1::dijkstra(0, i));
	}
	int ans2 = 0;
	// ans = dijkstra(0, 0);
	for(int i=0;i<4;i++) {
		ans2 = max(ans2, B2::dijkstra(0, i));
	}
	// assert(ans1>=ans2);
	cout << ans2 << "\n";
}

Compilation message

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12940 KB Output is correct
2 Correct 3 ms 13144 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12912 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Incorrect 2 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -