Submission #881071

#	Time	Username	Problem	Language	Result	Execution time	Memory
881071		user314	Cyberland (APIO23_cyberland)	C++17	0 / 100	363 ms	8124 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define pf push_front
#define fs first
#define sc second
#define printnm(_a) std::cout<<#_a<<' '<<_a<<'\n'
#define fri(_n) for (int i=0; i<_n; ++i)
#define fri1(_n) for (int i=1; i<=_n; ++i)
#define fr(_i,_n) for (int _i=0; _i<_n; ++_i)
#define fr1(_i,_n) for (int _i=1; _i<=_n; ++_i)

std::vector< std::pair<int,double> > adj [100005];
double dist [100005];
//bool visited [100005];
std::priority_queue< std::pair<double,int>, std::vector< std::pair<double,int> >, std::greater< std::pair<double,int> > > pq; //(-dist,node)

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
	memset(adj, 0, sizeof adj);
	for (int i=0; i<=N+5; ++i) dist[i] = 1e18;
	//memset(visited, 0, sizeof visited);
	//pq = std::priority_queue< std::pair<double,int>, std::vector< std::pair<double,int> >, std::greater< std::pair<double,int> > > ();

	if (N==1) return 0;

	fri(M) {adj[x[i]].pb({y[i],c[i]}); adj[y[i]].pb({x[i],c[i]});}

	pq.push({0,0});
	dist[0] = 0;

	int n=0,d=0;
	while(pq.size()) {
		std::pair<double,int> a = pq.top(); pq.pop();
		d = a.fs;
		n = a.sc;

		if (d != dist[n]) continue;
		for (auto i : adj[n]) {
			if (dist[i.fs] == 1e18 or (dist[i.fs] - d - i.sc) > 1e-6) {
				dist[i.fs] = d + i.sc;
				pq.push({dist[i.fs], i.fs});
			}
		}
	}

	if (dist[H] == 1e18) return -1;
	else return dist[H];
}

Compilation message (stderr)

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:21:27: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'class std::vector<std::pair<int, double> >' with no trivial copy-assignment; use assignment or value-initialization instead [-Wclass-memaccess]
   21 |  memset(adj, 0, sizeof adj);
      |                           ^
In file included from /usr/include/c++/10/vector:67,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:389:11: note: 'class std::vector<std::pair<int, double> >' declared here
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3