Submission #686543

#	Time	Username	Problem	Language	Result	Execution time	Memory
686543		pragmatist	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	130 ms	262144 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)1e5 + 7; // make sure this is right
const int M = (int)1e6 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

int n, m, k;
bool is[N];
ll dp[N], ans = INF;
vector<pii> g[N];

void dfs(int v, int pr) {
	if(is[v]) dp[v] = 0;
	else dp[v] = INF;
	vector<ll> e;
	for(auto [to, w] : g[v]) {
		if(to == pr) continue;
		dfs(to, v);
		e.pb(dp[to] + w);
	}
	sort(all(e));
	if(sz(e) > 1) dp[v] = min(dp[v], e[1]);
}

int travel_plan(int _n, int _m, int _r[][2], int _l[], int _k, int _p[]) {
	n = _n;
	m = _m;
	k = _k;
	for(int i = 0; i < m; ++i) {
		_r[i][0]++;
		_r[i][1]++;
		g[_r[i][0]].pb({_r[i][1], _l[i]});
		g[_r[i][1]].pb({_r[i][0], _l[i]});
	}
	for(int i = 0; i < k; ++i) {
		_p[i]++;
		is[_p[i]] = 1;
	}
	dfs(1, 1);
	return dp[1];	 	
}

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