oj.uz

Submission #1030973

# Submission time Handle Problem Language Result Execution time Memory
1030973 2024-07-22T13:07:28 Z vjudge1 City Mapping (NOI18_citymapping) C++17
0 / 100
 19 ms 604 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], deg[N];
pair<int, int> p[N], d[N];

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;
		deg[i] = 0;
	}
	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);

	set<int> st;
	for (int i = 1; i < n; i++) {
		int mn = d[i].first;
		int best = nd[0];
		for (int j : st) {
			if (mn == 1) break;

			int x = get_distance(j, d[i].second);
			if (x < mn) {
				mn = x;
				best = j;
			}
		}
		p[d[i].second] = make_pair(best, mn);
		
		if (++deg[best] == 3) {
			st.erase(best);
		}
		st.insert(d[i].second);
	}

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 604 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 604 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 Incorrect 19 ms 604 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -