oj.uz

Submission #1031020

# Submission time Handle Problem Language Result Execution time Memory
1031020 2024-07-22T13:32:06 Z vjudge1 City Mapping (NOI18_citymapping) C++17
25 / 100
 36 ms 692 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e3+3;

mt19937 rng(time(nullptr) + 69);

int n, nd[N], nd2[N], deg[N];
pair<int, int> p[N], d[N];
vector<int> adj[N];
bitset<N> r;

void dfs(int x) {
	r[x] = 1;
	for (int& y : adj[x]) {
		if (!r[y]) dfs(y);
	}
}

void find_roads(signed N, signed Q, signed A[], signed B[], signed W[]) {
	n = N;

	for (int i = 0; i < n; i++) {
		nd[i] = i+1;
		nd2[i] = i+1;

		deg[i] = 0;
		adj[i].clear();
	}
	shuffle(nd, nd+n, rng);
	
	d[0] = make_pair(0, nd[0]);
	for (int i = 1; i < n; i++) {
		d[i] = make_pair(get_distance(nd[0], nd[i]), nd[i]);
	}
	sort(d, d+n);

	for (int i = 1; i < n; i++) {
		int mn = d[i].first;
		int best = nd[0];
		
		shuffle(nd2, nd2+n, rng);
		r.reset();

		for (int j = 0; j < n && mn > 1; j++) {
			int x = nd2[j];
			if (!deg[x] || deg[x] >= 3 || r[x] || x == nd[0]) continue;

			int y = get_distance(x, d[i].second);
			if (y < mn) {
				mn = y;
				best = x;
			}
			if (y > d[i].first) {
				dfs(x);
			}
		}

		deg[best]++;
		deg[d[i].second]++;

		p[d[i].second] = make_pair(best, mn);

		adj[best].push_back(d[i].second);
	}

	for (int i = 0; i < N-1; i++) {
		A[i] = p[nd[i+1]].first;
		B[i] = nd[i+1];
		W[i] = p[nd[i+1]].second;
	}
	return;

	/*
	d[0] = make_pair(0, 1);
	for (int i = 2; i <= n; i++) {
		d[i-1] = make_pair(get_distance(1, i), i);
	}
	sort(d, d+n);

	int x = d[n-1].second;
	for (int i = 1; i <= n; i++) {
		if (x == i) d[i-1] = make_pair(0, x);
		else d[i-1] = make_pair(get_distance(x, i), i);
	}
	sort(d, d+n);

	for (int i = 0; i < n-1; i++) {
		A[i] = d[i].second;
		B[i] = d[i+1].second;
		W[i] = d[i+1].first - d[i].first;
	}
	*/
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 604 KB Correct: 150935 out of 500000 queries used.
2 Correct 17 ms 692 KB Correct: 133092 out of 500000 queries used.
3 Correct 16 ms 668 KB Correct: 148543 out of 500000 queries used.
4 Correct 14 ms 672 KB Correct: 126289 out of 500000 queries used.
5 Correct 21 ms 668 KB Correct: 233108 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 604 KB Correct: 150935 out of 500000 queries used.
2 Correct 17 ms 692 KB Correct: 133092 out of 500000 queries used.
3 Correct 16 ms 668 KB Correct: 148543 out of 500000 queries used.
4 Correct 14 ms 672 KB Correct: 126289 out of 500000 queries used.
5 Correct 21 ms 668 KB Correct: 233108 out of 500000 queries used.
6 Correct 35 ms 604 KB Correct: 257309 out of 500000 queries used.
7 Correct 28 ms 600 KB Correct: 303425 out of 500000 queries used.
8 Correct 32 ms 672 KB Correct: 281141 out of 500000 queries used.
9 Correct 29 ms 604 KB Correct: 261110 out of 500000 queries used.
10 Correct 36 ms 676 KB Correct: 457103 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Too many calls to get_distance().
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 604 KB Correct: 150935 out of 500000 queries used.
2 Correct 17 ms 692 KB Correct: 133092 out of 500000 queries used.
3 Correct 16 ms 668 KB Correct: 148543 out of 500000 queries used.
4 Correct 14 ms 672 KB Correct: 126289 out of 500000 queries used.
5 Correct 21 ms 668 KB Correct: 233108 out of 500000 queries used.
6 Correct 35 ms 604 KB Correct: 257309 out of 500000 queries used.
7 Correct 28 ms 600 KB Correct: 303425 out of 500000 queries used.
8 Correct 32 ms 672 KB Correct: 281141 out of 500000 queries used.
9 Correct 29 ms 604 KB Correct: 261110 out of 500000 queries used.
10 Correct 36 ms 676 KB Correct: 457103 out of 500000 queries used.
11 Incorrect 3 ms 604 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -