oj.uz

Submission #357857

# Submission time Handle Problem Language Result Execution time Memory
357857 2021-01-24T20:51:27 Z NachoLibre Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 966 ms 61964 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2796 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3180 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 2 ms 2796 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 2 ms 2796 KB Output is correct
9 Correct 4 ms 2924 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 6 ms 3180 KB Output is correct
13 Correct 5 ms 3180 KB Output is correct
14 Correct 2 ms 2796 KB Output is correct
15 Correct 3 ms 2796 KB Output is correct
16 Correct 631 ms 56644 KB Output is correct
17 Correct 87 ms 14572 KB Output is correct
18 Correct 110 ms 16108 KB Output is correct
19 Correct 966 ms 61964 KB Output is correct
20 Correct 323 ms 49772 KB Output is correct
21 Correct 44 ms 7916 KB Output is correct
22 Correct 355 ms 46316 KB Output is correct