oj.uz

Submission #357842

# Submission time Handle Problem Language Result Execution time Memory
357842 2021-01-24T19:14:20 Z NachoLibre Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 6 ms 2944 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 bp[N];

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;
	}
	if(z == -1 && p[x][1] != -1) {
		s.insert({p[x][1], x});
	} else if(z > p[x][1]) {
		if(bp[x]) exit(1);
		s.erase(s.find({z, x}));
		s.insert({p[x][1], x});
	}
}

void G(int x) {
	bp[x] = 1;
	for(int i = 0; i < (int)v[x].size(); ++i) {
		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) {
		p[c[i]][0] = p[c[i]][1] = 0;
		G(c[i]);
	}
	while(s.size()) {
		G((*s.begin()).second);
		s.erase(s.begin());
	}
	if(p[0][1] == -1) exit(1);
	return p[0][1];
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n = 5;
	int m = 7;
	int k = 2;
	int r[][2] = {0, 2, 0, 3, 3, 2, 2, 1, 0, 1, 0, 4, 3, 4};
	int l[] = {4, 3, 2, 10, 100, 7, 9};
	int c[] = {1, 3};
	cout << travel_plan(n, m, r, l, k, c) << endl;
	return 0;
}
#endif

Subtask #1
46.0 / 46.0

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2944 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 2 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Runtime error 6 ms 2924 KB Execution failed because the return code was nonzero
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2944 KB Output is correct
6 Correct 2 ms 2796 KB Output is correct
7 Correct 2 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Runtime error 6 ms 2924 KB Execution failed because the return code was nonzero
10 Halted 0 ms 0 KB -