oj.uz

Submission #465499

# Submission time Handle Problem Language Result Execution time Memory
465499 2021-08-16T08:55:43 Z MohamedFaresNebili Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n=N, m=M, k=K; vector<pair<int, long long>>adj[n]; 
    vector<long long>d(n, 1000000024); vector<bool>queued(n, false);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>pq;
    for(int l=0;l<m;l++) {
        int a=R[l][0], b=R[l][1]; long long w=L[l];
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
	vector<bool>used(n, false);
    for(int l=0;l<k;l++) {
        int a=P[l]; queued[a]=true;
        pq.push({0, a}); d[a]=0; used[a]=true;
    }
    vector<long long>len[n]; vector<int>income(n, 0); set<int>q;
    while(!pq.empty()) {
        int a=pq.top().second; pq.pop();
        for(auto u:adj[a]) {
            int to=u.first; long long s=u.second; 
			if(d[a]+s>d[to]) continue;
			q.insert(to); len[to].push_back(d[a]+s); 
        }
		
      	if(pq.empty()) {
			vector<int>vis;
          for(auto u:q) {
			  	int to=u; 
				if((int)len[to].size()==1) continue; 
                sort(len[to].begin(), len[to].end());
                pq.push({len[to][1], to});  d[to]=len[to][1];
                queued[to]=true; vis.push_back(to);
		  }
		  for(auto u:vis) { q.erase(u); }
        }
    }
    return (d[0]!=1000000024?d[0]:-1);
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -