oj.uz

Submission #674898

# Submission time Handle Problem Language Result Execution time Memory
674898 2022-12-26T13:30:44 Z QwertyPi City Mapping (NOI18_citymapping) C++14
25 / 100
 56 ms 28236 KB 
#include "citymapping.h"

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct edge{
	int u, v, w;
};
vector<edge> E;

const int MAXN = 1e3 + 11;
bool done[MAXN];
void solve(vector<int> v, vector<long long> d = {}, int pa = -1){
	if(v.size() == 1) return;
	for(auto i : v) done[i] = false;
	int rt;
	if(d.empty()){
		d.resize(MAXN);
		int id = rng() % v.size();
		rt = v[id]; d[rt] = 0; done[rt] = true;
		for(auto i : v){
			if(i != rt) d[i] = get_distance(rt, i);
		}
	}else{
		rt = pa;
		done[rt] = true;
	}
	for(int tr = 0; tr < 3; tr++){
		int ch = -1;
		for(auto i : v){
			if(!done[i] && (ch == -1 || d[ch] > d[i])) ch = i;
		}
		if(ch == -1) break; done[ch] = true; 
		E.push_back({rt, ch, d[ch]});
		vector<long long> d2(MAXN);
		vector<int> sub_tree {ch};
		for(auto i : v){
			if(!done[i] && i != ch) {
				if(tr < 2) d2[i] = get_distance(ch, i);
				if(d2[i] <= d[i]) sub_tree.push_back(i), done[i] = true;
			}
		}
		vector<long long> nd(MAXN);
		for(auto i : v){
			nd[i] = d[i] - d[ch];
		}
		solve(sub_tree, nd, ch);
	}
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	vector<int> v;
	for(int i = 1; i <= N; i++){
		v.push_back(i);
	}
	solve(v);
	for(int i = 0; i < E.size(); i++){
		A[i] = E[i].u, B[i] = E[i].v, W[i] = E[i].w;
	}
	return;
}

Compilation message

citymapping.cpp: In function 'void solve(std::vector<int>, std::vector<long long int>, int)':
citymapping.cpp:36:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   36 |   if(ch == -1) break; done[ch] = true;
      |   ^~
citymapping.cpp:36:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   36 |   if(ch == -1) break; done[ch] = true;
      |                       ^~~~
citymapping.cpp:37:30: warning: narrowing conversion of 'd.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)ch))' from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' [-Wnarrowing]
   37 |   E.push_back({rt, ch, d[ch]});
      |                              ^
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:60:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i = 0; i < E.size(); i++){
      |                 ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 28236 KB Correct: 476099 out of 500000 queries used.
2 Correct 28 ms 12244 KB Correct: 270350 out of 500000 queries used.
3 Correct 5 ms 1192 KB Correct: 27935 out of 500000 queries used.
4 Correct 3 ms 756 KB Correct: 14671 out of 500000 queries used.
5 Correct 8 ms 3220 KB Correct: 69472 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 28236 KB Correct: 476099 out of 500000 queries used.
2 Correct 28 ms 12244 KB Correct: 270350 out of 500000 queries used.
3 Correct 5 ms 1192 KB Correct: 27935 out of 500000 queries used.
4 Correct 3 ms 756 KB Correct: 14671 out of 500000 queries used.
5 Correct 8 ms 3220 KB Correct: 69472 out of 500000 queries used.
6 Correct 28 ms 18440 KB Correct: 276057 out of 500000 queries used.
7 Correct 19 ms 10836 KB Correct: 158239 out of 500000 queries used.
8 Correct 5 ms 1212 KB Correct: 25181 out of 500000 queries used.
9 Correct 4 ms 968 KB Correct: 20746 out of 500000 queries used.
10 Correct 11 ms 3588 KB Correct: 85037 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 852 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 852 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 56 ms 28236 KB Correct: 476099 out of 500000 queries used.
2 Correct 28 ms 12244 KB Correct: 270350 out of 500000 queries used.
3 Correct 5 ms 1192 KB Correct: 27935 out of 500000 queries used.
4 Correct 3 ms 756 KB Correct: 14671 out of 500000 queries used.
5 Correct 8 ms 3220 KB Correct: 69472 out of 500000 queries used.
6 Correct 28 ms 18440 KB Correct: 276057 out of 500000 queries used.
7 Correct 19 ms 10836 KB Correct: 158239 out of 500000 queries used.
8 Correct 5 ms 1212 KB Correct: 25181 out of 500000 queries used.
9 Correct 4 ms 968 KB Correct: 20746 out of 500000 queries used.
10 Correct 11 ms 3588 KB Correct: 85037 out of 500000 queries used.
11 Incorrect 2 ms 852 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -