답안 #953177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953177	2024-03-25T15:41:33 Z	WonderfulWhale	IOI 바이러스 (JOI21_fever)	C++17	11 / 100	6 ms	13192 KB

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);
	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #953177

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 8.0

Subtask #3 6.0 / 6.0

Subtask #4 0 / 6.0

Subtask #5 0 / 12.0

Subtask #6 0 / 32.0

Subtask #7 0 / 31.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 8.0

Subtask #3
6.0 / 6.0

Subtask #4
0 / 6.0

Subtask #5
0 / 12.0

Subtask #6
0 / 32.0

Subtask #7
0 / 31.0