oj.uz

Submission #953177

# Submission time Handle Problem Language Result Execution time Memory
953177 2024-03-25T15:41:33 Z WonderfulWhale IOI Fever (JOI21_fever) C++17
11 / 100
 6 ms 13192 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;

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);
	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(dis[y]==2e9) {
			// 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);
			// 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;
				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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12892 KB Output is correct
42 Correct 3 ms 12892 KB Output is correct
43 Correct 2 ms 12888 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Incorrect 2 ms 12892 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 13192 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 4 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 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12892 KB Output is correct
42 Correct 3 ms 12892 KB Output is correct
43 Correct 2 ms 12888 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Incorrect 2 ms 12892 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12892 KB Output is correct
42 Correct 3 ms 12892 KB Output is correct
43 Correct 2 ms 12888 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Incorrect 2 ms 12892 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12892 KB Output is correct
42 Correct 3 ms 12892 KB Output is correct
43 Correct 2 ms 12888 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Incorrect 2 ms 12892 KB Output isn't correct
46 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12948 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12888 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12892 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 3 ms 13148 KB Output is correct
18 Correct 3 ms 12900 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 5 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12900 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12888 KB Output is correct
26 Correct 3 ms 12888 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 2 ms 12892 KB Output is correct
29 Correct 3 ms 12892 KB Output is correct
30 Correct 3 ms 12892 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 2 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 2 ms 12892 KB Output is correct
36 Correct 3 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 2 ms 12892 KB Output is correct
39 Correct 2 ms 12892 KB Output is correct
40 Correct 3 ms 12892 KB Output is correct
41 Correct 3 ms 12892 KB Output is correct
42 Correct 3 ms 12892 KB Output is correct
43 Correct 2 ms 12888 KB Output is correct
44 Correct 3 ms 12892 KB Output is correct
45 Incorrect 2 ms 12892 KB Output isn't correct
46 Halted 0 ms 0 KB -