oj.uz

Submission #836493

# Submission time Handle Problem Language Result Execution time Memory
836493 2023-08-24T11:52:16 Z Liudas City Mapping (NOI18_citymapping) C++17
57 / 100
 310 ms 27776 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int get(int x){
	if(par[x] != x){
		return par[x] = get(par[x]);
	}
	return x;
}
void merge(int a, int b){
	par[get(a)] = get(b);
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	if(Q == 500000){
		par.resize(N + 5);
		iota(par.begin(), par.end(), 0);
		vector<vector<long long>> tree;
		int p = 0;
		for(int i = 0; i < N; i ++){
			for(int j = i + 1; j < N; j ++){
				tree.push_back({get_distance(i+1, j+1), i+1, j+1});
			}
		}
		sort(tree.begin(), tree.end());
		for(auto i : tree){
			int a = i[0], b = i[1], c = i[2];
			if(get(b) != get(c)){
				merge(b,c);
				A[p] = b;
				B[p] = c;
				W[p++] = a; 
			}
		}
	}
	else{
		vector<pair<long long, long long>> dist(N, {0, 0});
		for(int i = 1; i < N; i ++){
			dist[i] = {get_distance(1, i + 1), i};
		}
		sort(dist.rbegin(), dist.rend());
		for(int i = 1; i < N; i ++){
			dist[i] = {get_distance(dist[i].second + 1, dist[0].second + 1), dist[i].second};
		}
		long long total = 0;
		dist[0] = {0, dist[0].second};
		sort(dist.begin(), dist.end());
		for(int i = 1; i < N; i ++){
			W[i-1] = dist[i].first - total;
			A[i-1] = dist[i-1].second + 1;
			B[i-1] = dist[i].second + 1;
			total += W[i-1];
		}
	}
	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 27776 KB Correct: 498501 out of 500000 queries used.
2 Correct 231 ms 27708 KB Correct: 499500 out of 500000 queries used.
3 Correct 249 ms 27496 KB Correct: 492528 out of 500000 queries used.
4 Correct 192 ms 27520 KB Correct: 494515 out of 500000 queries used.
5 Correct 310 ms 27668 KB Correct: 498501 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 27776 KB Correct: 498501 out of 500000 queries used.
2 Correct 231 ms 27708 KB Correct: 499500 out of 500000 queries used.
3 Correct 249 ms 27496 KB Correct: 492528 out of 500000 queries used.
4 Correct 192 ms 27520 KB Correct: 494515 out of 500000 queries used.
5 Correct 310 ms 27668 KB Correct: 498501 out of 500000 queries used.
6 Correct 275 ms 27608 KB Correct: 495510 out of 500000 queries used.
7 Correct 207 ms 27624 KB Correct: 497503 out of 500000 queries used.
8 Correct 218 ms 27604 KB Correct: 497503 out of 500000 queries used.
9 Correct 217 ms 27492 KB Correct: 495510 out of 500000 queries used.
10 Correct 240 ms 27512 KB Correct: 496506 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
3 Correct 1 ms 484 KB Correct: 1998 out of 12000 queries used.
4 Correct 2 ms 468 KB Correct: 1984 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
2 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
3 Correct 1 ms 484 KB Correct: 1998 out of 12000 queries used.
4 Correct 2 ms 468 KB Correct: 1984 out of 12000 queries used.
5 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
6 Correct 1 ms 468 KB Correct: 1994 out of 12000 queries used.
7 Correct 1 ms 468 KB Correct: 1990 out of 12000 queries used.
8 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
9 Correct 1 ms 468 KB Correct: 1992 out of 12000 queries used.
10 Correct 1 ms 468 KB Correct: 1986 out of 12000 queries used.

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 27776 KB Correct: 498501 out of 500000 queries used.
2 Correct 231 ms 27708 KB Correct: 499500 out of 500000 queries used.
3 Correct 249 ms 27496 KB Correct: 492528 out of 500000 queries used.
4 Correct 192 ms 27520 KB Correct: 494515 out of 500000 queries used.
5 Correct 310 ms 27668 KB Correct: 498501 out of 500000 queries used.
6 Correct 275 ms 27608 KB Correct: 495510 out of 500000 queries used.
7 Correct 207 ms 27624 KB Correct: 497503 out of 500000 queries used.
8 Correct 218 ms 27604 KB Correct: 497503 out of 500000 queries used.
9 Correct 217 ms 27492 KB Correct: 495510 out of 500000 queries used.
10 Correct 240 ms 27512 KB Correct: 496506 out of 500000 queries used.
11 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
12 Correct 1 ms 468 KB Correct: 1984 out of 12000 queries used.
13 Correct 1 ms 484 KB Correct: 1998 out of 12000 queries used.
14 Correct 2 ms 468 KB Correct: 1984 out of 12000 queries used.
15 Correct 1 ms 468 KB Correct: 1980 out of 12000 queries used.
16 Correct 1 ms 468 KB Correct: 1994 out of 12000 queries used.
17 Correct 1 ms 468 KB Correct: 1990 out of 12000 queries used.
18 Correct 1 ms 468 KB Correct: 1998 out of 12000 queries used.
19 Correct 1 ms 468 KB Correct: 1992 out of 12000 queries used.
20 Correct 1 ms 468 KB Correct: 1986 out of 12000 queries used.
21 Correct 1 ms 468 KB Correct: 1990 out of 25000 queries used.
22 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
23 Halted 0 ms 0 KB -