oj.uz

Submission #836548

# Submission time Handle Problem Language Result Execution time Memory
836548 2023-08-24T12:44:48 Z Liudas City Mapping (NOI18_citymapping) C++17
0 / 100
 1 ms 468 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<pair<long long, long long>> tree;
	vector<long long> init(N+5);
	int p = 0;
	for(int i = 1; i < N; i ++){
		tree.push_back({get_distance(1, i+1), i+1});
		init[i+1] = tree.back().first;
	}
	sort(tree.begin(), tree.end());
	vector<int> picks(N+20);
	set<long long> ends;
	for(auto [j, i] : tree){
		int picked = false;
		for(auto r : ends){
			long long t = get_distance(r, i);
			if(init[i] == init[r] + t){
				picked = true;
				A[p] = i;
				B[p] = r;
				W[p++] = t;
				picks[r]++;
				ends.insert(i);
				if(picks[r] == 2){
					ends.erase(r);
				}
				break;
			}
		}
		if(!picked){
			ends.insert(i);
			A[p] = 1;
			B[p] = i;
			W[p++] = init[i];
		}
	}
	return;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -