oj.uz

Submission #896497

# Submission time Handle Problem Language Result Execution time Memory
896497 2024-01-01T14:50:27 Z LCJLY Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 2000 ms 4440 KB 
#include "crocodile.h"
//
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define int long long

int32_t travel_plan(int32_t n, int32_t m, int32_t r[][2], int32_t w[], int32_t k, int32_t p[]){
	vector<pii>adj[n+5];
	for(int x=0;x<m;x++){
		adj[r[x][0]].push_back({r[x][1],w[x]});
		adj[r[x][1]].push_back({r[x][0],w[x]});
	}
	
	pii dist[n+5];
	memset(dist,-1,sizeof(dist));
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int x=0;x<k;x++){
		dist[p[x]]={0,0};
		pq.push({0,p[x]});
	}
	
	bool visited[n+5];
	memset(visited,0,sizeof(visited));
	while(!pq.empty()){
		pii cur=pq.top();
		pq.pop();
		int x=cur.second;
		int d=cur.first;
		if(dist[x].second!=d) continue;
		visited[x]=true;
		
		for(auto it:adj[x]){
			int nx=it.first;
			int nd=d+it.second;
			if(dist[nx].first==-1||nd<=dist[nx].first){
				dist[nx].second=dist[nx].first;
				dist[nx].first=nd;
				pq.push({nd,nx});
			}
			else{
				dist[nx].second=nd;
				pq.push({nd,nx});
			}
		}
	}
	
	if(dist[0].second!=-1){
		return dist[0].second;
	}
	else{
		assert(0);
		return -1;
	}
}

Compilation message

crocodile.cpp: In function 'int32_t travel_plan(int32_t, int32_t, int32_t (*)[2], int32_t*, int32_t, int32_t*)':
crocodile.cpp:16:29: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'pii' {aka 'struct std::pair<int, int>'} with no trivial copy-assignment [-Wclass-memaccess]
   16 |  memset(dist,-1,sizeof(dist));
      |                             ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from crocodile.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'pii' {aka 'struct std::pair<int, int>'} declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4440 KB Time limit exceeded
2 Halted 0 ms 0 KB -