Submission #148125

#	Time	Username	Problem	Language	Result	Execution time	Memory
148125		WhipppedCream	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	748 ms	63116 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define ii pair<int, int>
#define st first
#define nd second
#define maxn 100005
vector< ii > adj[maxn];
bool mark[maxn];
ii dist[maxn];
struct node
{
	int u, d;
	node(){}
	node(int _u, int _d)
	{
		u = _u;
		d = _d;
	}
	bool operator < (node other) const
	{
		return d> other.d;
	}
};
int travel_plan(int n, int m, int R[][2], int *L, int k, int *P)
{
    priority_queue< node > pq;
    for(int i = 0; i< n; i++)
    {
        dist[i].st = dist[i].nd = 1e9;
        pq.push(node(i, 1e9));
    }
	for(int i = 0; i< m; i++)
	{
		adj[R[i][0]].push_back(ii(R[i][1], L[i]));
		adj[R[i][1]].push_back(ii(R[i][0], L[i]));
	}
	for(int i = 0; i< k; i++)
	{
		pq.push(node(P[i], 0));
		dist[P[i]].st = dist[P[i]].nd = 0;
	}
	while(!pq.empty())
	{
		node x = pq.top();
		pq.pop();
		int u = x.u;
        if(x.d != dist[u].nd) continue;
		for(int i = 0; i< (int) adj[u].size(); i++)
		{
			ii k = adj[u][i];
			int v = k.st, w = k.nd;
			int nw = w+dist[u].nd;
			if(nw < dist[v].st)
			{
				dist[v].nd = dist[v].st;
				dist[v].st = nw;
				pq.push(node(v, dist[v].nd));
			}
			else if(nw < dist[v].nd)
			{
				dist[v].nd = nw;
				pq.push(node(v, dist[v].nd));
			}
		}
	}
	return dist[0].nd;
}

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