oj.uz

Submission #836276

# Submission time Handle Problem Language Result Execution time Memory
836276 2023-08-24T09:37:36 Z gustason City Mapping (NOI18_citymapping) C++14
57 / 100
 123 ms 19220 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;
const int nax = 1002;
using ll = long long;

struct Dsu {
	ll par[nax];
	ll sz[nax];
	
	Dsu() {
		for(int i = 0; i < nax; i++) {
			par[i] = i;
			sz[i] = 1;
		}
	}
	
	int find(int v) {
		if (v == par[v]) {
			return v;
		}
		return par[v] = find(par[v]);
	}
	
	bool unite(int a, int b) {
		 a = find(a), b = find(b);
		 if (a == b) return false;
		 
		 if (sz[b] > sz[a]) swap(a, b);
		 par[b] = a;
		 sz[a] += sz[b];
		 return true;
	}
};

ll dist[nax][nax];

ll get_dist(int a, int b) {
	if (dist[a][b] != 0) {
		return dist[a][b];
	}
	return dist[a][b] = get_distance(a, b);
}

void brute(int N, int* A, int* B, int* W) {
	vector<array<ll, 3>> d;
	for(int i = 1; i <= N; i++) {
		for(int j = i+1; j <= N; j++) {
			get_dist(i, j);
			d.push_back({dist[i][j], i, j});
		}
	}
	
	sort(d.begin(), d.end());
	Dsu dsu;
	
	int idx = 0;
	for(auto& i : d) {
		if (dsu.unite(i[1], i[2])) {
			A[idx] = i[1];
			B[idx] = i[2];
			W[idx] = i[0];
			idx++;
		}
	}
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if (Q == 500000) {
		brute(N, A, B, W);
		return;
	}
	vector<array<ll, 2>> d;
	for(int i = 2; i <= N; i++) {
		d.push_back({get_dist(1, i), i});
	}
		
	sort(d.begin(), d.end());
	
	//for(auto& i : d) {
		//cout << i[0] << " " << i[1] << "\n";
	//}
	
	A[0] = 1, B[0] = d[0][1], W[0] = d[0][0];
	if (N == 2) return;
		
	vector<int> child{B[0]};
		
	for(int i = 1; i < N-1; i++) {
		bool found = false;
		for(auto& u : child) {
			if (d[i][0] == get_dist(1, u) + get_dist(u, d[i][1])) {
				found = true;
				A[i] = u;
				B[i] = d[i][1];
				u = B[i];
				break;
			}
		}
				
		if (!found) {
			A[i] = 1;
			B[i] = d[i][1];
			child.push_back(B[i]);
			assert(get_dist(1, d[i][1]) == d[i][0]);
		}
		
		W[i] = get_dist(A[i], B[i]);
	}
	
	//for(int i = 0; i < N; i++) {
		//cout << A[i] << " " << B[i] << " " << W[i] << "\n";
	//}
	
	//for(auto& i : d) {
		//cout << i[0] << " " << i[1] << "\n";
	//}
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 19204 KB Correct: 498501 out of 500000 queries used.
2 Correct 109 ms 19220 KB Correct: 499500 out of 500000 queries used.
3 Correct 108 ms 18992 KB Correct: 492528 out of 500000 queries used.
4 Correct 103 ms 18992 KB Correct: 494515 out of 500000 queries used.
5 Correct 123 ms 19148 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 19204 KB Correct: 498501 out of 500000 queries used.
2 Correct 109 ms 19220 KB Correct: 499500 out of 500000 queries used.
3 Correct 108 ms 18992 KB Correct: 492528 out of 500000 queries used.
4 Correct 103 ms 18992 KB Correct: 494515 out of 500000 queries used.
5 Correct 123 ms 19148 KB Correct: 498501 out of 500000 queries used.
6 Correct 89 ms 19040 KB Correct: 495510 out of 500000 queries used.
7 Correct 97 ms 19152 KB Correct: 497503 out of 500000 queries used.
8 Correct 91 ms 19112 KB Correct: 497503 out of 500000 queries used.
9 Correct 82 ms 19116 KB Correct: 495510 out of 500000 queries used.
10 Correct 94 ms 19020 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Correct: 2897 out of 12000 queries used.
2 Correct 3 ms 4692 KB Correct: 2754 out of 12000 queries used.
3 Correct 3 ms 4948 KB Correct: 2312 out of 12000 queries used.
4 Correct 3 ms 4948 KB Correct: 2299 out of 12000 queries used.
5 Correct 3 ms 4564 KB Correct: 2151 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Correct: 2897 out of 12000 queries used.
2 Correct 3 ms 4692 KB Correct: 2754 out of 12000 queries used.
3 Correct 3 ms 4948 KB Correct: 2312 out of 12000 queries used.
4 Correct 3 ms 4948 KB Correct: 2299 out of 12000 queries used.
5 Correct 3 ms 4564 KB Correct: 2151 out of 12000 queries used.
6 Correct 6 ms 4948 KB Correct: 2517 out of 12000 queries used.
7 Correct 4 ms 4948 KB Correct: 2376 out of 12000 queries used.
8 Correct 3 ms 4564 KB Correct: 2193 out of 12000 queries used.
9 Correct 3 ms 4692 KB Correct: 2218 out of 12000 queries used.
10 Correct 3 ms 4820 KB Correct: 2297 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 19204 KB Correct: 498501 out of 500000 queries used.
2 Correct 109 ms 19220 KB Correct: 499500 out of 500000 queries used.
3 Correct 108 ms 18992 KB Correct: 492528 out of 500000 queries used.
4 Correct 103 ms 18992 KB Correct: 494515 out of 500000 queries used.
5 Correct 123 ms 19148 KB Correct: 498501 out of 500000 queries used.
6 Correct 89 ms 19040 KB Correct: 495510 out of 500000 queries used.
7 Correct 97 ms 19152 KB Correct: 497503 out of 500000 queries used.
8 Correct 91 ms 19112 KB Correct: 497503 out of 500000 queries used.
9 Correct 82 ms 19116 KB Correct: 495510 out of 500000 queries used.
10 Correct 94 ms 19020 KB Correct: 496506 out of 500000 queries used.
11 Correct 3 ms 4436 KB Correct: 2897 out of 12000 queries used.
12 Correct 3 ms 4692 KB Correct: 2754 out of 12000 queries used.
13 Correct 3 ms 4948 KB Correct: 2312 out of 12000 queries used.
14 Correct 3 ms 4948 KB Correct: 2299 out of 12000 queries used.
15 Correct 3 ms 4564 KB Correct: 2151 out of 12000 queries used.
16 Correct 6 ms 4948 KB Correct: 2517 out of 12000 queries used.
17 Correct 4 ms 4948 KB Correct: 2376 out of 12000 queries used.
18 Correct 3 ms 4564 KB Correct: 2193 out of 12000 queries used.
19 Correct 3 ms 4692 KB Correct: 2218 out of 12000 queries used.
20 Correct 3 ms 4820 KB Correct: 2297 out of 12000 queries used.
21 Correct 3 ms 5076 KB Correct: 2474 out of 25000 queries used.
22 Incorrect 5 ms 4608 KB Too many calls to get_distance().
23 Halted 0 ms 0 KB -