Submission #1221782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221782		sleepntsheep	Crocodile's Underground City (IOI11_crocodile)	C11	100 / 100	303 ms	37832 KiB

crocodile

#include "crocodile.h"
#include <stdio.h>
#include <string.h>

#define N 100000
#define M 1000000
#define N_ (1 << 17)

int n_, hd[N], e[M * 2 + 2], Ln[M * 2 + 2], c[M * 2 + 2]
	, ii, dp[1 + N], tt[N_ << 1], dq[1 + N];

void add(int u, int v, int w)
{
	int i = ++ii;
	e[i] = v, Ln[i] = hd[u], c[i] = w, hd[u] = i;
}

int ij(int i, int j) {
	return dp[i] < dp[j] ? i : j;
}
void pul(int i) {
	tt[i] = ij(tt[i << 1], tt[i << 1 | 1]);
}
void fix(int i) {
	for (i += n_; i >>= 1; )
		pul(i);
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for (int i = 0; i < m; ++i)
		add(R[i][0], R[i][1], L[i]), add(R[i][1], R[i][0], L[i]);

	memset(dq, 0x3f, sizeof dq);
	memset(dp, 0x3f, sizeof dp);
	dp[n]++;
	dq[n]++;
	for (int i = 0; i < K; ++i)
		dp[P[i]] = 0, dq[P[i]] = 0;

	for (n_ = 1; n_ < n; n_ <<= 1);

	for (int i = 0; i < n_; ++i)
		tt[i + n_] = i < n ? i : n;

	for (int i = n_ - 1; i >= 1; --i)
		pul(i);
 
	for (int it = 0;; ++it) {
		int u = tt[1];
		if (u == n)
			break;
		tt[u + n_] = n;
		fix(u);

		for (int w, v, j = hd[u]; j; j = Ln[j]) {
			v = e[j], w = c[j];
			if (dq[v] > dp[u] + w) {
				dp[v] = dq[v], dq[v] = dp[u] + w;
				fix(v);
			} else if (dp[v] > dp[u] + w) {
				dp[v] = dp[u] + w;
				fix(v);
			}
		}
	}

  return dp[0];
}

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