oj.uz

Submission #924102

# Submission time Handle Problem Language Result Execution time Memory
924102 2024-02-08T13:05:32 Z pcc City Mapping (NOI18_citymapping) C++14
25 / 100
 97 ms 10944 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

#define pll pair<ll,ll>
#define fs first
#define sc second
#define ll long long
#define pii pair<int,int>
const int mxn = 1010;
vector<pair<ll,pii>> edges;
int dsu[mxn];

int root(int k){
	return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	for(int i = 1;i<=N;i++){
		for(int j = i+1;j<=N;j++){
			edges.push_back(make_pair(get_distance(i,j),make_pair(i,j)));
		}
	}
	for(int i = 1;i<=N;i++)dsu[i] = i;
	sort(edges.begin(),edges.end());
	int pt = 0;
	for(auto &i:edges){
		int a = i.sc.fs,b = i.sc.sc;
		if(root(a) == root(b))continue;
		A[pt] = a,B[pt] = b,W[pt] = i.fs;
		dsu[root(a)] = root(b);
		pt++;
	}
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10940 KB Correct: 498501 out of 500000 queries used.
2 Correct 89 ms 9132 KB Correct: 499500 out of 500000 queries used.
3 Correct 86 ms 10696 KB Correct: 492528 out of 500000 queries used.
4 Correct 82 ms 9160 KB Correct: 494515 out of 500000 queries used.
5 Correct 94 ms 9544 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 10940 KB Correct: 498501 out of 500000 queries used.
2 Correct 89 ms 9132 KB Correct: 499500 out of 500000 queries used.
3 Correct 86 ms 10696 KB Correct: 492528 out of 500000 queries used.
4 Correct 82 ms 9160 KB Correct: 494515 out of 500000 queries used.
5 Correct 94 ms 9544 KB Correct: 498501 out of 500000 queries used.
6 Correct 70 ms 10440 KB Correct: 495510 out of 500000 queries used.
7 Correct 81 ms 10944 KB Correct: 497503 out of 500000 queries used.
8 Correct 70 ms 9692 KB Correct: 497503 out of 500000 queries used.
9 Correct 64 ms 9156 KB Correct: 495510 out of 500000 queries used.
10 Correct 76 ms 10432 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 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 860 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 97 ms 10940 KB Correct: 498501 out of 500000 queries used.
2 Correct 89 ms 9132 KB Correct: 499500 out of 500000 queries used.
3 Correct 86 ms 10696 KB Correct: 492528 out of 500000 queries used.
4 Correct 82 ms 9160 KB Correct: 494515 out of 500000 queries used.
5 Correct 94 ms 9544 KB Correct: 498501 out of 500000 queries used.
6 Correct 70 ms 10440 KB Correct: 495510 out of 500000 queries used.
7 Correct 81 ms 10944 KB Correct: 497503 out of 500000 queries used.
8 Correct 70 ms 9692 KB Correct: 497503 out of 500000 queries used.
9 Correct 64 ms 9156 KB Correct: 495510 out of 500000 queries used.
10 Correct 76 ms 10432 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 2 ms 860 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -