Submission #414696

#	Time	Username	Problem	Language	Result	Execution time	Memory
414696		jeqcho	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	508 ms	51352 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpi;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define fi first
#define se second

int const n=1e5+4;
vpi adj[n];
bitset<n> vis;
pii d[n];
int const INF=2e9;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	F0R(i,M)
	{
		int u=R[i][0];
		int v=R[i][1];
		int w=L[i];
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	F0R(i,N)
	{
		d[i]={INF,INF};
	}
	priority_queue<pii>q;
	F0R(i,K)
	{
		d[P[i]].fi=0;
		d[P[i]].se=0;
		q.push({0,P[i]});
	}
	while(!vis[0])
	{
		int u = q.top().se;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		trav(e,adj[u])
		{
			int cand = d[u].se+e.se;
			if(cand < d[e.fi].se)
			{
				if(cand<d[e.fi].fi)
				{
					d[e.fi].se=d[e.fi].fi;
					d[e.fi].fi=cand;
				}
				else
				{
					d[e.fi].se=cand;
				}
				q.push({-d[e.fi].se,e.fi});
			}
		}
	}
	return d[0].se;
}

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