Submission #640560

#	Time	Username	Problem	Language	Result	Execution time	Memory
640560		ymm	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	650 ms	59984 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

static const int N = 100'010;
static const int inf = 1e9;
static vector<pii> A[N];
static int vc[N][2];
static int dis[N];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	Loop (i,0,m) {
		A[r[i][0]].push_back({r[i][1], l[i]});
		A[r[i][1]].push_back({r[i][0], l[i]});
	}
	set<pii> s;
	fill (dis, dis+N, inf);
	Loop (i,0,N) vc[i][0] = vc[i][1] = inf;
	Loop (i,0,k) {
		dis[p[i]] = 0;
		s.insert({0, p[i]});
	}
	while (s.size()) {
		auto [d, v] = *s.begin();
		s.erase(s.begin());
		for (auto [u, w] : A[v]) {
			if (d + w < vc[u][1])
				vc[u][1] = d + w;
			if (vc[u][1] < vc[u][0])
				swap(vc[u][0], vc[u][1]);
			if (vc[u][1] < dis[u]) {
				s.erase({dis[u], u});
				dis[u] = vc[u][1];
				s.insert({dis[u], u});
			}
		}
	}
	return dis[0];
}

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