Submission #72606

#	Time	Username	Problem	Language	Result	Execution time	Memory
72606		MrTEK	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	857 ms	45208 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left isc+isc
#define right isc+isc+1
#define mid (l+r)/2
#define FAfi_IO ios_base::sync_with_fidio(false);
#define escl '\n'
#define bit __builtin_popcount

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef long long int lli;
typedef pair<int,int> pii;

struct node {
	int x,cost;
};

bool operator < (node a,node b) {
	return a.cost > b.cost;
}

priority_queue <node> Q;

vector <pii> ed[N];

int mn2[N],mn[N],ans[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0 ; i < M ; i++) {
		ed[R[i][0]].pb(mp(R[i][1],L[i]));
		ed[R[i][1]].pb(mp(R[i][0],L[i]));
	}
	memset(mn,63,sizeof mn);
	memset(mn2,63,sizeof mn2);
	for (int i = 0 ; i < K ; i++) {
		if (P[i] == 0) return 0;
		Q.push({P[i],0});
		mn[P[i]] = mn2[P[i]] = 0;
	}
	while(len(Q)) {
		auto it = Q.top();
		Q.pop();
		if (it.cost > mn2[it.x]) continue;
		for (auto i : ed[it.x]) {
			int u = i.fi;
			int v = i.sc;
			int tut = mn2[u];
			mn2[u] = min(mn2[u],v + it.cost);
			if (mn2[u] < mn[u]) swap(mn2[u],mn[u]);
			if (mn2[u] != tut)
				Q.push({u,mn2[u]});
		}
	}
	return mn2[0];
}

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