Submission #357857

#	Time	Username	Problem	Language	Result	Execution time	Memory
357857		NachoLibre	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	966 ms	61964 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
#include "crocodile.h"
#endif

const int N = 100005;
vector<pair<int, int>> v[N];
long long p[N][2];
set<pair<long long, int>> s;
bool vy[N], et[N];
#ifdef wambule
bool bo;
#endif

void D(int x, long long y) {
	long long z = p[x][1];
	if(p[x][0] == -1 || y < p[x][0]) {
		p[x][1] = p[x][0];
		p[x][0] = y;
	} else if(p[x][1] == -1 || y < p[x][1]) {
		p[x][1] = y;
	}
	// cout << "[333] " << x << " " << y << " " << p[x][0] << " " << p[x][1] << endl;
	if(z != p[x][1]) {
		// if(s.find({z, x}) != s.end()) s.erase(s.find({z, x}));
		if(z != -1) s.erase(s.find({z, x}));
		#ifdef wambule
		else if(z != -1) {
			cout << "[1] " << x << " " << z << " " << p[x][1] << endl;
			bo = 1;
		}
		#endif
		s.insert({p[x][1], x});
	}
}

void G(int x) {
	// cout << "[22] " << x << " " << p[x][1] << endl;
	for(int i = 0; i < (int)v[x].size(); ++i) {
		if(!et[v[x][i].first])
			D(v[x][i].first, p[x][1] + v[x][i].second);
	}
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int c[]) {
	for(int i = 0; i < n; ++i) {
		p[i][0] = p[i][1] = -1;
	}
	for(int i = 0; i < m; ++i) {
		v[r[i][0]].push_back({r[i][1], l[i]});
		v[r[i][1]].push_back({r[i][0], l[i]});
	}
	for(int i = 0; i < k; ++i) {
		et[c[i]] = 1;
	}
	for(int i = 0; i < k; ++i) {
		if(vy[c[i]]) continue;
		vy[c[i]] = 1;
		p[c[i]][0] = p[c[i]][1] = 0;
		G(c[i]);
	}
	long long bb = 0;
	while(s.size()) {
		if((*s.begin()).first < bb) exit(1);
		G((*s.begin()).second);
		bb = (*s.begin()).first;
		s.erase(s.begin());
	}
	if(p[0][1] == -1) exit(1);
	return p[0][1];
}

#ifdef wambule
const int M = 1000006;
mt19937_64 rnd(time(0));
long long R(long long l, long long r) {
	return l + rnd() % (r - l + 1);
}

int n = 5;
int m = 7;
int k = 2;
int r[M][2] = {0, 2, 0, 3, 3, 2, 2, 1, 0, 1, 0, 4, 3, 4};
int l[M] = {4, 3, 2, 10, 100, 7, 9};
int c[N] = {1, 3};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	// for(int i = 0; i < N; ++i) {
	// 	p[i][0] = p[i][1] = -1;
	// }
	// while(1) {
	// 	int x, y;
	// 	cin >> x;
	// 	cout << "[] " << p[x][0] << " " << p[x][1] << endl;
	// 	cin >> y;
	// 	D(x, y);
	// 	cout << "[] " << p[x][0] << " " << p[x][1] << endl;
	// }
	n = 10;
	m = 20;
	k = R(1, n - 1);
	for(int i = 0; i < k; ++i) c[i] = R(1, n - 1);
	for(int i = 0; i < m; ++i) {
		l[i] = R(1, 10);
		r[i][0] = R(0, n - 1);
		do {
			r[i][1] = R(0, n - 1);
		} while(r[i][1] == r[i][0]);
	}
	// cout << n << " " << m << " " << k << "\n";
	// for(int i = 0; i < k; ++i) {
	// 	cout << c[i] << " ";
	// }
	// cout << "\n";
	// for(int i = 0; i < m; ++i) {
	// 	cout << r[i][0] << " " << r[i][1] << " " << l[i] << "\n";
	// }
	///
	freopen("Untitledfile.txt", "r", stdin);
	cin >> n >> m >> k;
	for(int i = 0; i < k; ++i) cin >> c[i];
	for(int i = 0; i < m; ++i) cin >> r[i][0] >> r[i][1] >> l[i];
	cout << travel_plan(n, m, r, l, k, c) << endl;
	return 0;
}
/*

10 20 6
8 3 8 5 4 2
0 5 10
8 4 4
3 9 2
8 7 5
6 9 6
6 1 5
5 8 8
2 7 10
8 0 9
8 1 3
4 1 5
8 3 2
3 9 1
9 2 2
9 8 2
4 1 5
3 4 8
3 8 9
0 1 1
5 4 5

*/
#endif

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