oj.uz

답안 #953159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953159 2024-03-25T15:10:39 Z WonderfulWhale IOI 바이러스 (JOI21_fever) C++17
6 / 100
 13 ms 25948 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) {
	for(int i=0;i<MAXN;i++) dis[i] = 1e18;
	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;
				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";
	assert(ans==ANS);
	cerr << ans << " " << 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 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 4 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12912 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 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Runtime error 13 ms 25948 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -