Submission #1143820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143820		buzdi	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	6 ms	10308 KiB

crocodile

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

#define ll long long

using namespace std;

const int NMAX = 1e5;
const ll INF = 1e18;

struct PQElement {
	int node, parent, edge_parent;
	ll d;
	bool operator < (const PQElement &other) const {
		return other.d < d;
	}
};

vector<pair<int, int>> g[NMAX + 1];
vector<pair<int, int>> g1[NMAX + 1];
int n, m;
vector<ll> d[NMAX + 1];
vector<pair<int, int>> parents[NMAX + 1];
char is_end[NMAX + 1];
ll dp[NMAX + 1][2];
int indegree[NMAX + 1];

void Dijkstra(int start) {
	priority_queue<PQElement> pq;
	pq.push({start, 0, 0, 0});
	while(!pq.empty()) {
		auto [node, parent, edge_parent, curent_d] = pq.top();
		pq.pop();

		if(d[node].size() < 1) {
			d[node].push_back(curent_d);
			parents[node].emplace_back(parent, edge_parent);

			if(!is_end[node]) {
				for(auto [next_node, edge_d] : g[node]) {
					pq.push({next_node, node, edge_d, curent_d + edge_d});
				}
			}
		}
	}
}

void CreateDAG() {
	for(int i = 2; i <= n; i++) {
		for(auto [j, c] : parents[i]) {
			g1[i].emplace_back(j, c);
		}
	}

	for(int i = 1; i <= n; i++) {
		sort(g1[i].begin(), g1[i].end());
		g1[i].erase(unique(g1[i].begin(), g1[i].end()), g1[i].end());
		for(auto [j, c] : g1[i]) {
			indegree[j]++;
		}
	}
}

void Update(ll dp[], ll dp_value) {
	if(dp_value < dp[0]) {
		dp[1] = dp[0];
		dp[0] = dp_value;
	}
	else if(dp_value < dp[1]) {
		dp[1] = dp_value;
	}
}

void SolveDP() {
	for(int i = 1; i <= n; i++) {
		dp[i][0] = dp[i][1] = INF;
	}

	queue<int> q;
	for(int i = 1; i <= n; i++) {
		if(!indegree[i]) {
			q.push(i);
			if(is_end[i]) {
				dp[i][0] = dp[i][1] = 0;
			}
		}
	}

	while(!q.empty()) {
		int node = q.front();
		q.pop();

		for(auto [next_node, edge_d] : g1[node]) {
			Update(dp[next_node], dp[node][1] + edge_d);
			indegree[next_node]--;
			if(!indegree[next_node]) {
				q.push(next_node);
			}
		}
	}
}

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++) {
		int a = R[i][0]; a++;
		int b = R[i][1]; b++;
		int c = L[i];

		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}

	for(int i = 0; i < K; i++) {
		P[i]++;
		is_end[P[i]] = 1;
	}

	Dijkstra(1);

	// for(int i = 1; i <= n; i++) {
	// 	for(auto [j, c] : parents[i]) {
	// 		cout << i << ' ' << j << ' ' << c << '\n';
	// 	}
	// }

	CreateDAG();
	SolveDP();

	// for(int i = 1; i <= n; i++) {
	// 	for(auto [j, c] : g1[i]) {
	// 		cout << i - 1 << ' ' << j - 1 << ' ' << c << '\n';
	// 	}
	// }

	return dp[1][1];
}

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