oj.uz

Submission #846471

# Submission time Handle Problem Language Result Execution time Memory
846471 2023-09-07T15:17:45 Z vjudge1 ČVENK (COI15_cvenk) C++17
0 / 100
 3000 ms 524288 KB 
#include <bits/stdc++.h>
#define lint long long
#define endl '\n'
#define pii pair<int, int>
#define pll pair<lint, lint>
#define For(i,n) for (int i = 0; i < n; i++)
#define FOR For(i, n)
using namespace std;

const int N = 1e5;

map<pii, bool> vis[N];
map<pii, lint> dist;
map<pii, int> visc;

lint fdepth[N] = {};


void validpush(queue<pair<int, pair<lint, pii>>>& q, int tourist, lint depth, int x, int y) {
	if (x >= 1e9 || y >= 1e9) return;
	if (x < 0 || y < 0) return;
	if ((x & y)) return;
	if (vis[tourist][{x,y}]) return;
	q.push({tourist, {depth, {x,y}}});
}

int main() {
	int n; cin >> n;
	vector<pii> ts(n);
	for (int i = 0; i < n; i++) {
		int a,b; cin >> a >> b;
		a--; b--;
		ts[i] = {a,b};
	}

	FOR fdepth[i] = 2e18;

	// tourist, depth, x, y
	queue<pair<int, pair<lint, pair<int, int>>>> q;
	FOR q.push({i, {0ll, ts[i]}}); lint mn = 2e18;
	while (!q.empty()) {
		int tourist = q.front().first;
		lint depth = q.front().second.first;
		pii cord = q.front().second.second;
		int x = cord.first;
		int y = cord.second;
		q.pop();
		if (vis[tourist][cord]) continue;
		vis[tourist][cord] = 1;
		visc[cord]++;
		dist[cord] += depth;
		if (depth > fdepth[tourist]) {
			// no more
			continue;
		}
		if (visc[cord] == n) {
			fdepth[tourist] = depth;
			mn = min(dist[cord], mn);
			continue;
		}

		validpush(q, tourist, depth + 1, x+1, y);
		validpush(q, tourist, depth + 1, x, y+1);
		validpush(q, tourist, depth + 1, x-1, y);
		validpush(q, tourist, depth + 1, x, y-1);
	}

	cout << mn << endl;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 308384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3037 ms 274372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 377544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2790 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -