oj.uz

Submission #846416

# Submission time Handle Problem Language Result Execution time Memory
846416 2023-09-07T14:30:20 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, int> vis[N];
map<pii, int> visc;
map<pii, lint> dist;

void validpush(queue<pair<int, pair<lint, pii>>>& q, int tourist, int 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 x,y; cin >> x >> y;
		ts[i] = {x,y};
	}

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

	cout << mn << endl;
}

Compilation message

cvenk.cpp: In function 'int main()':
cvenk.cpp:32:55: warning: variable 'fdepth' set but not used [-Wunused-but-set-variable]
   32 |  queue<pair<int, pair<lint, pair<int, int>>>> q; lint fdepth = -1; lint mn = 2e18;
      |                                                       ^~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 315552 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 3055 ms 290884 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 3051 ms 407688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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