Submission #799865

#	Time	Username	Problem	Language	Result	Execution time	Memory
799865		Sohsoh84	Crocodile's Underground City (IOI11_crocodile)	C++17	89 / 100	888 ms	262144 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X		first
#define Y		second
#define sep		' '
#define all(x)		(x).begin(), (x).end()
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

ll dist[MAXN], n, m;
set<pll> adj_st[MAXN], adj_st_r[MAXN];
vector<pll> adj[MAXN];
priority_queue<pll, vector<pll>, greater<pll>> pq;

inline void check(int v) {
	if (int(adj_st[v].size()) > 1 && (next(adj_st[v].begin()) -> X) < dist[v]) {
		dist[v] = next(adj_st[v].begin()) -> X; 
		pq.push({dist[v], v});
	}
}

inline void fix(int v) {
	for (auto [u, l] : adj[v]) {
		auto it = adj_st_r[u].lower_bound(pll(v, -1));
		if (it != adj_st_r[u].end() && it -> X == v) {
			ll d = it -> Y;
			adj_st_r[u].erase(it);
			adj_st[u].erase(pll(d, v));
		}

		adj_st_r[u].insert({v, dist[v] + l});
		adj_st[u].insert({dist[v] + l, v});
		check(u);
	}
} 

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N, m = M;
	for (int i = 0; i < m; i++) {
		adj[R[i][0]].push_back({R[i][1], L[i]});
		adj[R[i][1]].push_back({R[i][0], L[i]});
	}

	memset(dist, 63, sizeof dist);
	for (int i = 0; i < K; i++) {
		int v = P[i];
		dist[v] = 0;
		pq.push({0, v});
	}

	while (!pq.empty()) {
		auto [d_v, v] = pq.top();
		pq.pop();
		if (d_v != dist[v]) continue;
		if (v == 2) {
		}
		fix(v);
	}

	return dist[0];
}

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