oj.uz

Submission #924752

# Submission time Handle Problem Language Result Execution time Memory
924752 2024-02-09T15:57:18 Z pcc City Mapping (NOI18_citymapping) C++17
25 / 100
 15 ms 8788 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;
ll dist[mxn][mxn];
queue<vector<int>> q;

ll f(int a,int b){
	return dist[a][b]?dist[a][b]:dist[a][b] = dist[b][a] = get_distance(a,b);
}

inline void calc(vector<int> v){
	//for(auto &i:v)cout<<i<<',';cout<<endl;
	if(v.size()<2)return;
	if(v.size()==2){
		edges.push_back(make_pair(f(v[0],v[1]),make_pair(v[0],v[1])));
		return;
	}
	random_shuffle(v.begin(),v.end());
	int a = v[0];pll sm = make_pair(f(a,v[1]),1ll*v[1]);
	for(int i = 1;i<v.size();i++)sm = min(sm,make_pair(f(a,v[i]),1ll*v[i]));
	int b = sm.sc;
	edges.push_back(make_pair(sm.fs,make_pair(a,b)));
	vector<int> lv,rv;
	for(auto &i:v){
		if(i == a||i == b)continue;
		if(f(a,i)<f(b,i))lv.push_back(i);
		else rv.push_back(i);
	}
	lv.push_back(a);
	rv.push_back(b);
	q.push(lv);
	q.push(rv);
	return;
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
	srand(7122);
	q.push({});
	for(int i = 1;i<=N;i++)q.front().push_back(i);
	while(!q.empty()){
		auto v = q.front();
		q.pop();
		calc(v);
	}
	assert(edges.size() == N-1);
	for(int i = 0;i<edges.size();i++){
		W[i] = edges[i].fs;
		A[i] = edges[i].sc.fs;
		B[i] = edges[i].sc.sc;
	}
	return;
}

Compilation message

citymapping.cpp: In function 'void calc(std::vector<int>)':
citymapping.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 1;i<v.size();i++)sm = min(sm,make_pair(f(a,v[i]),1ll*v[i]));
      |                ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from citymapping.cpp:2:
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:54:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |  assert(edges.size() == N-1);
      |         ~~~~~~~~~~~~~^~~~~~
citymapping.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Correct: 19718 out of 500000 queries used.
2 Correct 7 ms 8540 KB Correct: 42733 out of 500000 queries used.
3 Correct 13 ms 8280 KB Correct: 166256 out of 500000 queries used.
4 Correct 15 ms 8484 KB Correct: 192834 out of 500000 queries used.
5 Correct 8 ms 8540 KB Correct: 67460 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8536 KB Correct: 19718 out of 500000 queries used.
2 Correct 7 ms 8540 KB Correct: 42733 out of 500000 queries used.
3 Correct 13 ms 8280 KB Correct: 166256 out of 500000 queries used.
4 Correct 15 ms 8484 KB Correct: 192834 out of 500000 queries used.
5 Correct 8 ms 8540 KB Correct: 67460 out of 500000 queries used.
6 Correct 4 ms 8788 KB Correct: 18486 out of 500000 queries used.
7 Correct 5 ms 8540 KB Correct: 31129 out of 500000 queries used.
8 Correct 11 ms 8508 KB Correct: 115417 out of 500000 queries used.
9 Correct 12 ms 8280 KB Correct: 152460 out of 500000 queries used.
10 Correct 10 ms 8284 KB Correct: 69351 out of 500000 queries used.

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8284 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 3 ms 8284 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 4 ms 8536 KB Correct: 19718 out of 500000 queries used.
2 Correct 7 ms 8540 KB Correct: 42733 out of 500000 queries used.
3 Correct 13 ms 8280 KB Correct: 166256 out of 500000 queries used.
4 Correct 15 ms 8484 KB Correct: 192834 out of 500000 queries used.
5 Correct 8 ms 8540 KB Correct: 67460 out of 500000 queries used.
6 Correct 4 ms 8788 KB Correct: 18486 out of 500000 queries used.
7 Correct 5 ms 8540 KB Correct: 31129 out of 500000 queries used.
8 Correct 11 ms 8508 KB Correct: 115417 out of 500000 queries used.
9 Correct 12 ms 8280 KB Correct: 152460 out of 500000 queries used.
10 Correct 10 ms 8284 KB Correct: 69351 out of 500000 queries used.
11 Incorrect 3 ms 8284 KB Too many calls to get_distance().
12 Halted 0 ms 0 KB -