Submission #910572

#	Time	Username	Problem	Language	Result	Execution time	Memory
910572		oblantis	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	652 ms	55996 KiB

crocodile

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
#include "crocodile.h"
int dst[maxn][2];
vt<pii> g[maxn];
int travel_plan(int n, int m, int adj[][2], int l[], int k, int p[]){
	for(int i = 0; i < m; i++){
		g[adj[i][0]].pb({adj[i][1], l[i]});
		g[adj[i][1]].pb({adj[i][0], l[i]});
	}
	for(int i = 0; i < n; i++){
		dst[i][0] = dst[i][1] = inf;
	}
	set<pii> pq;
	for(int i = 0; i < k; i++){
		dst[p[i]][0] = dst[p[i]][1] = 0;
		pq.insert({0, p[i]});
	}
	while(!pq.empty()){
		pii nw = *pq.begin();
		pq.erase(pq.begin());
		for(auto i : g[nw.ss]){
			if(nw.ff + i.ss >= dst[i.ff][1])continue;
			if(pq.find({dst[i.ff][1], i.ff}) != pq.end())pq.erase(pq.find({dst[i.ff][1], i.ff}));
			if(nw.ff + i.ss < dst[i.ff][0]){
				dst[i.ff][1] = dst[i.ff][0];
				dst[i.ff][0] = nw.ff + i.ss;
			}
			else dst[i.ff][1] = nw.ff + i.ss;
			pq.insert({dst[i.ff][1], i.ff});
		}
	}
	return dst[0][1];
}
//void solve() {
	//int n, m, k;
	//cin >> n >> m >> k;
	//int r[m][2], l[m], p[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);
//}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}

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