Submission #1320920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320920		tkm_algorithms	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	188 ms	327680 KiB

crocodile

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

using namespace std;
using ll = long long;
//#define int ll
//using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;
const int NMAX = 1010;
const int inf = 1e9+10;

void solve() {
	
}

vector<pair<int, int>> g[NMAX];
bool specific[NMAX];
int dp[NMAX];

void dfs(int node, int par) {
	if (specific[node])dp[node] = 0;
	int mn = inf, mn2 = inf;
	for (auto [son, weight]: g[node]) {
		if (son == par)continue;
		dfs(son, node);
		if (dp[son]+weight < mn)mn2 = mn, mn = dp[son]+weight;
		else mn2 = min(mn2, dp[son]+weight);
	}
	
	dp[node] = min(dp[node], mn2);
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(specific, false, sizeof specific);
	rep(i, 0, M)
		g[R[i][0]].push_back({R[i][1], L[i]}),
		g[R[i][1]].push_back({R[i][0], L[i]});
		
	rep(i, 0, N)dp[i] = inf;
	rep(i, 0, K)specific[P[i]] = 1;
	dfs(0, 0);
	return dp[0];
}

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