oj.uz

Submission #836072

# Submission time Handle Problem Language Result Execution time Memory
836072 2023-08-24T06:58:29 Z gustason City Mapping (NOI18_citymapping) C++14
9 / 100
 105 ms 10296 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

const int nax = 1002;

struct Dsu {
	int par[nax];
	int 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;
	}
};

int dist[nax][nax];

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<array<int, 3>> d;
	for(int i = 1; i <= N; i++) {
		for(int j = i+1; j <= N; j++) {
			dist[i][j] = get_distance(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++;
		}
	}
		
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 10296 KB Correct: 498501 out of 500000 queries used.
2 Correct 99 ms 10288 KB Correct: 499500 out of 500000 queries used.
3 Correct 103 ms 10172 KB Correct: 492528 out of 500000 queries used.
4 Correct 91 ms 10252 KB Correct: 494515 out of 500000 queries used.
5 Correct 105 ms 10288 KB Correct: 498501 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 10296 KB Correct: 498501 out of 500000 queries used.
2 Correct 99 ms 10288 KB Correct: 499500 out of 500000 queries used.
3 Correct 103 ms 10172 KB Correct: 492528 out of 500000 queries used.
4 Correct 91 ms 10252 KB Correct: 494515 out of 500000 queries used.
5 Correct 105 ms 10288 KB Correct: 498501 out of 500000 queries used.
6 Incorrect 80 ms 10296 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 788 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 2 ms 788 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 102 ms 10296 KB Correct: 498501 out of 500000 queries used.
2 Correct 99 ms 10288 KB Correct: 499500 out of 500000 queries used.
3 Correct 103 ms 10172 KB Correct: 492528 out of 500000 queries used.
4 Correct 91 ms 10252 KB Correct: 494515 out of 500000 queries used.
5 Correct 105 ms 10288 KB Correct: 498501 out of 500000 queries used.
6 Incorrect 80 ms 10296 KB Reported list of edges differ from actual.
7 Halted 0 ms 0 KB -