Submission #1143754

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

crocodile

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

#define ll long long

using namespace std;

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

vector<pair<int, int>> g[NMAX + 1];
ll dp[NMAX + 1];

void DFS(int node, int dad = 0) {
	if(g[node].size() == 1) {
		return;
	}
	
	// dp[node] = INF;
	ll dp1 = INF, dp2 = INF;
	for(auto [next_node, edge_value] : g[node]) {
		if(next_node != dad) {
			DFS(next_node, node);
			if(dp[next_node] + edge_value < dp1) {
				dp2 = dp1;
				dp1 = dp[next_node] + edge_value;
			}
			else if(dp[next_node] + edge_value < dp2) {
				dp2 = dp[next_node] + edge_value;
			}
		}
	}
	dp[node] = dp2;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for(int i = 0; i < M; i++) {
		int a = R[i][0]; a++;
		int b = R[i][1]; b++;
		int c = L[i];
		
		// cout << a << ' ' << b << ' ' << c << '\n';

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

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

	DFS(1);
	return dp[1];
}

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