oj.uz

Submission #211364

# Submission time Handle Problem Language Result Execution time Memory
211364 2020-03-20T08:12:27 Z socho Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 2000 ms 77376 KB 
#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
// #define int long long

int n, m;
const int MXN = 100005;
vector<pair<int, int> > adj[MXN];
bool ter[MXN], assign[MXN];
int dist[MXN];
int via[MXN];



int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  
	n = N, m = M;
	for (int i=0; i<m; i++) {
		int a, b, w;
		a = R[i][0], b = R[i][1], w = L[i];
		adj[a].push_back(make_pair(b, w));
		adj[b].push_back(make_pair(a, w));
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pro;
	vector<int> poss[MXN];
	bool done[MXN];
	
	for (int i=0; i<MXN; i++) dist[i] = INT_MAX;
	
	int k = K;
	for (int i=0; i<k; i++) {
		int x = P[i];
		ter[x] = true;
		dist[x] = 0;
		done[x] = true;
		pro.push(make_pair(0, x));
	}

	
	while (!pro.empty()) {
		
		int di = pro.top().first;
		int no = pro.top().second;
		pro.pop();
		
		if (dist[no] < di) continue; // do not relax

		if (poss[no].size() >= 2 && !done[no]) {
			// can assign second dist, first relaxing
			done[no] = true;
			sort(poss[no].begin(), poss[no].end());
			dist[no] = poss[no][1];
		}
		
		if (done[no] && !assign[no]) {
			assign[no] = true;
			// can access adjs
			for (int i=0; i<adj[no].size(); i++) {
				// cout << "add option: " << no << " to " << adj[no][i].first << endl;
				int f = adj[no][i].second;
				poss[adj[no][i].first].push_back(f + dist[no]);
				if (poss[adj[no][i].first].size() >= 2) {
					sort(poss[adj[no][i].first].begin(), poss[adj[no][i].first].end());
					pro.push(make_pair(poss[adj[no][i].first][1], adj[no][i].first));
				}
			}
		}

	}
	
	assert(dist[0] != INT_MAX);
	return dist[0];
  
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i=0; i<adj[no].size(); i++) {
                  ~^~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5376 KB Output is correct
2 Correct 7 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5376 KB Output is correct
2 Correct 7 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 13 ms 5812 KB Output is correct
10 Correct 7 ms 5504 KB Output is correct
11 Correct 9 ms 5632 KB Output is correct
12 Correct 26 ms 6008 KB Output is correct
13 Correct 22 ms 6144 KB Output is correct
14 Correct 8 ms 5504 KB Output is correct
15 Correct 9 ms 5632 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5376 KB Output is correct
2 Correct 7 ms 5376 KB Output is correct
3 Correct 8 ms 5504 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 8 ms 5504 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 13 ms 5812 KB Output is correct
10 Correct 7 ms 5504 KB Output is correct
11 Correct 9 ms 5632 KB Output is correct
12 Correct 26 ms 6008 KB Output is correct
13 Correct 22 ms 6144 KB Output is correct
14 Correct 8 ms 5504 KB Output is correct
15 Correct 9 ms 5632 KB Output is correct
16 Correct 1711 ms 73280 KB Output is correct
17 Correct 118 ms 19064 KB Output is correct
18 Correct 160 ms 20344 KB Output is correct
19 Correct 1496 ms 77376 KB Output is correct
20 Execution timed out 2089 ms 61764 KB Time limit exceeded
21 Halted 0 ms 0 KB -