oj.uz

Submission #321759

# Submission time Handle Problem Language Result Execution time Memory
321759 2020-11-13T09:47:37 Z wind_reaper City Mapping (NOI18_citymapping) C++17
9 / 100
 104 ms 16492 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;
struct DSU{
	vector<int> e;
	void init(int n){
		e = vector<int>(n, -1);
	}

	int get(int x){
		return (e[x] < 0 ? x : e[x] = get(e[x]));
	}

	bool same_set(int x, int y){
		return get(x) == get(y);
	}

	bool unite(int x, int y){
		x = get(x), y = get(y);
		if(e[x] < e[y])
			swap(x, y);

		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<pair<int, int>, long long>> edges((N*(N-1))/2);
	int c = 0; 
	for(int i = 1; i <= N; i++)
		for(int j = i+1; j <= N; j++)
			edges[c++] = {{i, j}, get_distance(i, j)};

	sort(edges.begin(), edges.end(), [&](pair<pair<int, int>, long long> &a, pair<pair<int, int>, long long> &b){
		if(a.second < b.second) return true;
		return false;
	});

	DSU s;
	s.init(N);
	int m = 0;
	for(int i = 0; i < c; i++){
		if(s.same_set(edges[i].first.first, edges[i].first.second)) continue;
		s.unite(edges[i].first.first, edges[i].first.second);
		A[m] = edges[i].first.first, B[m] = edges[i].first.second, W[m] = edges[i].second;
		m++; 
	}
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 77 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 63 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 58 ms 8300 KB Correct: 494515 out of 500000 queries used.
5 Correct 74 ms 8300 KB Correct: 498501 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 77 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 63 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 58 ms 8300 KB Correct: 494515 out of 500000 queries used.
5 Correct 74 ms 8300 KB Correct: 498501 out of 500000 queries used.
6 Correct 89 ms 8428 KB Correct: 495510 out of 500000 queries used.
7 Runtime error 104 ms 16492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8172 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 6 ms 8172 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 86 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 77 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 63 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 58 ms 8300 KB Correct: 494515 out of 500000 queries used.
5 Correct 74 ms 8300 KB Correct: 498501 out of 500000 queries used.
6 Correct 89 ms 8428 KB Correct: 495510 out of 500000 queries used.
7 Runtime error 104 ms 16492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -