Submission #743894

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

crocodile

#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second  

#include "crocodile.h"
const int maxn = 1006;
vector<vector<pii>> adj(maxn);
vector<pii> ans(maxn);
vector<int> win(maxn, 0);
void get(int u,int from) {
	if (win[u]) {
		ans[u].fi = 0; ans[u].se = 0;
		return;
	}
	vector<int> res;
	for (auto& v : adj[u]) {
		if (v.se == from) continue;
		get(v.se,u);
		res.push_back(ans[v.se].se+v.fi);
	} 
	sort(res.begin(), res.end());
	ans[u].fi = res[0];
	if (res.size() == 1) {
		ans[u].se = res[0];
	}
	else {
		ans[u].se = res[1];
	}
}
int travel_plan(int n, int m, int r[][2], int w[], int k, int p[])
{
	for (int i = 0; i < m; i++) {
		adj[r[i][0]].push_back(mp(w[i], r[i][1]));
		adj[r[i][1]].push_back(mp(w[i], r[i][0]));
	}
	for (int i = 0; i < k; i++) {
		win[p[i]] = 1;
	}
	get(0,-1);
	return ans[0].se;
} 

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