Submission #337098

#	Time	Username	Problem	Language	Result	Execution time	Memory
337098		enerelt14	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	785 ms	67420 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
using namespace std;
vector<pair<int, int> >adj[100005];
priority_queue<pair<int, int> >pq;
bool vis[100005]={0};
int viz[100005]={0};
int path[100005];
void dijkstra(){
	while(!pq.empty()){
		int u=pq.top().ss;
		int cost=-pq.top().ff;
		pq.pop();
		if (viz[u]==1){
			vis[u]=1;
			path[u]=cost;
			for (int i=0;i<adj[u].size();i++){
				int v=adj[u][i].ff;
				int cst=adj[u][i].ss;
				if (!vis[v])pq.push(mp(-(cost+cst), v));
			}
		}
		viz[u]++;
	}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (int i=0;i<M;i++){
		adj[R[i][0]].pb(mp(R[i][1], L[i]));
		adj[R[i][1]].pb(mp(R[i][0], L[i]));
	}
	for (int i=0;i<K;i++){
		pq.push(mp(0, P[i]));
		viz[P[i]]=1;
	}
	while(!pq.empty()){
		int u=pq.top().ss;
		int cost=-pq.top().ff;
		pq.pop();
		if (viz[u]==1){
			vis[u]=1;
			path[u]=cost;
			for (int i=0;i<adj[u].size();i++){
				int v=adj[u][i].ff;
				int cst=adj[u][i].ss;
				if (!vis[v])pq.push(mp(-(cost+cst), v));
			}
		}
		viz[u]++;
	}
	return path[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for (int i=0;i<adj[u].size();i++){
      |                 ~^~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for (int i=0;i<adj[u].size();i++){
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11