oj.uz

Submission #321807

# Submission time Handle Problem Language Result Execution time Memory
321807 2020-11-13T11:56:47 Z wind_reaper City Mapping (NOI18_citymapping) C++17
9 / 100
 108 ms 16620 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;
	vector<int> count(N);
	for(int i = 0; i < c; i++){
		if(s.same_set(edges[i].first.first, edges[i].first.second) || count[edges[i].first.first] >= 3 || count[edges[i].first.second] >= 3) 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;
		count[A[m]]++, count[B[m]]++;
		m++; 
		if(m == N-1) break;
	}
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 76 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 64 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 56 ms 8172 KB Correct: 494515 out of 500000 queries used.
5 Correct 72 ms 8300 KB Correct: 498501 out of 500000 queries used.

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 76 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 64 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 56 ms 8172 KB Correct: 494515 out of 500000 queries used.
5 Correct 72 ms 8300 KB Correct: 498501 out of 500000 queries used.
6 Correct 87 ms 8300 KB Correct: 495510 out of 500000 queries used.
7 Runtime error 108 ms 16620 KB Execution killed with signal 6 (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 8 ms 8124 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 8 ms 8124 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 81 ms 8300 KB Correct: 498501 out of 500000 queries used.
2 Correct 76 ms 8300 KB Correct: 499500 out of 500000 queries used.
3 Correct 64 ms 8172 KB Correct: 492528 out of 500000 queries used.
4 Correct 56 ms 8172 KB Correct: 494515 out of 500000 queries used.
5 Correct 72 ms 8300 KB Correct: 498501 out of 500000 queries used.
6 Correct 87 ms 8300 KB Correct: 495510 out of 500000 queries used.
7 Runtime error 108 ms 16620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -