oj.uz

Submission #1063892

# Submission time Handle Problem Language Result Execution time Memory
1063892 2024-08-18T05:40:40 Z Luvidi City Mapping (NOI18_citymapping) C++17
25 / 100
 90 ms 8904 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

#define ll long long

const int maxn=1e3;
int par[maxn+1];

int rep(int x){
	if(x==par[x])return x;
	return par[x]=rep(par[x]);
}

bool join(int x,int y){
	x=rep(x);
	y=rep(y);
	par[x]=y;
	return x!=y;
}

void find_roads(int n, int q, int a[], int b[], int w[]) {
	vector<pair<ll,pair<int,int>>> edge;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ll d=get_distance(i,j);
			edge.push_back({d,{i,j}});
		}
		par[i]=i;
	}
	sort(edge.begin(),edge.end());
	int cnt=0;
	for(auto [d,p]:edge){
		auto[x,y]=p;
		if(join(x,y)){
			a[cnt]=x;
			b[cnt]=y;
			w[cnt]=d;
			cnt++;
		}
	}
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8896 KB Correct: 498501 out of 500000 queries used.
2 Correct 83 ms 8904 KB Correct: 499500 out of 500000 queries used.
3 Correct 80 ms 8904 KB Correct: 492528 out of 500000 queries used.
4 Correct 76 ms 8904 KB Correct: 494515 out of 500000 queries used.
5 Correct 90 ms 8900 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8896 KB Correct: 498501 out of 500000 queries used.
2 Correct 83 ms 8904 KB Correct: 499500 out of 500000 queries used.
3 Correct 80 ms 8904 KB Correct: 492528 out of 500000 queries used.
4 Correct 76 ms 8904 KB Correct: 494515 out of 500000 queries used.
5 Correct 90 ms 8900 KB Correct: 498501 out of 500000 queries used.
6 Correct 64 ms 8808 KB Correct: 495510 out of 500000 queries used.
7 Correct 71 ms 8904 KB Correct: 497503 out of 500000 queries used.
8 Correct 64 ms 8868 KB Correct: 497503 out of 500000 queries used.
9 Correct 61 ms 8904 KB Correct: 495510 out of 500000 queries used.
10 Correct 68 ms 8904 KB Correct: 496506 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 83 ms 8896 KB Correct: 498501 out of 500000 queries used.
2 Correct 83 ms 8904 KB Correct: 499500 out of 500000 queries used.
3 Correct 80 ms 8904 KB Correct: 492528 out of 500000 queries used.
4 Correct 76 ms 8904 KB Correct: 494515 out of 500000 queries used.
5 Correct 90 ms 8900 KB Correct: 498501 out of 500000 queries used.
6 Correct 64 ms 8808 KB Correct: 495510 out of 500000 queries used.
7 Correct 71 ms 8904 KB Correct: 497503 out of 500000 queries used.
8 Correct 64 ms 8868 KB Correct: 497503 out of 500000 queries used.
9 Correct 61 ms 8904 KB Correct: 495510 out of 500000 queries used.
10 Correct 68 ms 8904 KB Correct: 496506 out of 500000 queries used.
11 Incorrect 1 ms 860 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -