Submission #804552

#	Time	Username	Problem	Language	Result	Execution time	Memory
804552		LIF	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	566 ms	74964 KiB

crocodile

#include <bits/stdc++.h>
#include <queue>
using namespace std;
int cnt = 0;
struct edg
{
	int to;
	int next;
	long long int val;
}edge[2000005];
struct node
{
	long long int val1;
	long long int val2;
	int id;
};
node dis[300005];
int head[300005];
void add(int x,int y,int val)
{
	cnt++;
	edge[cnt].to = y;
	edge[cnt].next = head[x];
	edge[cnt].val = val;
	head[x] = cnt; 
}
priority_queue<node> q;
bool operator < (node x,node y)
{
	return x.val2 > y.val2;
}
bool vis[300005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	//cout<<"yeah"<<endl;
	for(int i=0;i<M;i++)add(R[i][0],R[i][1],L[i]);
	for(int i=0;i<M;i++)add(R[i][1],R[i][0],L[i]);
	for(int i=0;i<N;i++)
	{
		dis[i].val1 = 1e18;
		dis[i].val2 = 1e18;
		dis[i].id = i;
	}
	for(int i=0;i<K;i++)
	{
		dis[P[i]].val1 = 0;
		dis[P[i]].val2 = 0;
	}
	for(int i=0;i<K;i++)
	{
		q.push(dis[P[i]]);
	} 
	while(q.empty() == false)
	{
		node now = q.top();
		int val = now.val2;
		q.pop();
		if(vis[now.id] == true)continue;
		vis[now.id] = true;
		for(int i=head[now.id];i!=0;i=edge[i].next)
		{
			int to = edge[i].to;
			if(dis[to].val1 > dis[now.id].val2 + edge[i].val)
			{
				dis[to].val2 = dis[to].val1;
				dis[to].val1 = dis[now.id].val2 + edge[i].val;
				if(vis[to] == false)q.push(dis[to]);
			}
			else
			{
				if(dis[to].val2 > dis[now.id].val2 + edge[i].val)
				{
					dis[to].val2 = dis[now.id].val2 + edge[i].val;
					if(vis[to] == false)q.push(dis[to]);
				}
			}
		}
	}
  return dis[0].val2;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:56:7: warning: unused variable 'val' [-Wunused-variable]
   56 |   int val = now.val2;
      |       ^~~

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