Submission #130644

#	Time	Username	Problem	Language	Result	Execution time	Memory
130644		SpeedOfMagic	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	7 ms	4216 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 1e5 + 1;
const ll inf = 1e9;
vector<pair<int, int>> g[N]; //init me

ll res[N];
pair<int, int> rf[N];
void dijkstra(int st) {
	for (int i = 0; i < N; i++) {
		rf[i] = {-1, -1};
		res[i] = inf;
	}
	res[st] = 0;
	
    priority_queue<pair<int, int>> nxt;
    nxt.push({-res[st], st});

    while (!nxt.empty()) {
        int cur = nxt.top().second;
        int cost = -nxt.top().first;
        nxt.pop();
        if (cost != res[cur])
            continue;

        for (pair<int, int> i : g[cur])
            if (res[i.first] > cost + i.second) {
                res[i.first] = cost + i.second;
				rf[i.first] = {cur, i.second};
                nxt.push({-res[i.first], i.first});
            }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	for (int i = 0; i < M; i++) {
		g[R[i][0]].push_back({R[i][1], L[i]});
		g[R[i][1]].push_back({R[i][0], L[i]});
	}
	dijkstra(0);
	char exit[N];
	memset(exit, 0, sizeof exit);
	for (int i = 0; i < K; i++)
		exit[P[i]] = 1;
	
	char rem[N];
	memset(rem, 0, sizeof rem);
	for (bool again = 1; again;) {
		again = 0;
		dijkstra(0);
		int opt = -1;
		for (int i = 0; i < N; i++)
			if (exit[i] && (opt == -1 || res[opt] > res[i]))
				opt = i;
		//cout << res[opt] << " " << opt << endl;
		while (rf[opt].first != -1) {
			int prev = rf[opt].first;
			//cout << prev << endl;
			if (!rem[prev]) {
				again = 1;
				vector<pair<int, int>> nxtVec;
				bool erased = 0;
				for (auto i : g[prev])
					if (!erased && i.first == opt && i.second == rf[opt].second)
						erased = 1;
					else
						nxtVec.push_back(i);
				assert(erased);
				rem[prev] = 1;
				g[prev] = nxtVec;
			}
			opt = prev;
		}
	}
	
	dijkstra(0);
	int ans = inf;
	for (int i = 0; i < N; i++)
		if (exit[i] && (ans > res[i]))
			ans = res[i];
	
	return ans;
}

//31 11
//g++ -std=c++14 grader.cpp crocodile.cpp

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