Submission #199127

#	Time	Username	Problem	Language	Result	Execution time	Memory
199127		godwind	Crocodile's Underground City (IOI11_crocodile)	C++14	46 / 100	251 ms	262148 KiB

crocodile

// #include "grader.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;

#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 100 * 1000 + 228;
const int INF = 1e9 + 228;

int n, m, k;
vector< pair<int, int> > g[N];

int mn1[N], mn2[N];

bool tet = 0;

bool relax(int i, int x) {
	tet = 0;
	if (x < mn1[i]) {
		if (mn1[i] < mn2[i]) tet = 1;
		mn2[i] = mn1[i];
		mn1[i] = x;
	} else if (x < mn2[i]) {
		mn2[i] = x;
		tet = 1;
	}
	return tet;
}

int dp[N];

void dfs(int v, int par = -1) {
	vector<int> x;
	for (pair<int, int> go : g[v]) {
		int to = go.first;
		int w = go.second;
		if (to == par) continue;
		dfs(to, v);
		x.push_back(w + dp[to]);
	}
	if (x.empty()) dp[v] = 0;
	else {
		sort(x.begin(), x.end());
		dp[v] = x[1];
	}
}

int travel_plan(int nn, int mm, int R[][2], int L[], int K, int P[]) {
	n = nn;
	m = mm;
	k = K;
	for (int i = 0; i < m; ++i) {
		g[R[i][0]].emplace_back(R[i][1], L[i]);
		g[R[i][1]].emplace_back(R[i][0], L[i]);
	}
	dfs(0);
	return dp[0];
	// for (int i = 0; i < n; ++i) {
	// 	mn1[i] = mn2[i] = INF;
	// }
	// priority_queue< pair<int, int> > q;
	// for (int i = 0; i < k; ++i) {
	// 	mn1[P[i]] = mn2[P[i]] = 0;
	// 	q.push({0, P[i]});
	// }
	// while (!q.empty()) {
	// 	pair<int, int> f = q.top();
	// 	q.pop();
	// 	int v = f.second;
	// 	int to, w;
	// 	for (pair<int, int> go : g[v]) {
	// 		to = go.first, w = go.second;
	// 		if (relax(to, mn2[v] + w)) {
	// 			q.push({-mn2[to], to});
	// 		}
	// 	}
	// }

	// return mn2[0];
}

// int r[100][2], l[1000], p[1000];

// signed main() {
// 	cin >> n >> m >> k;
// 	for (int i = 0; i < m; ++i) {
// 		cin >> r[i][0] >> r[i][1] >> l[i];
// 	}
// 	for (int i = 0; i < k; ++i) {
// 		cin >> p[i];
// 	}
// 	cout << travel_plan(n, m, r, l, k, p) << '\n';
// 	return 0;
// }

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