Submission #465482

#	Time	Username	Problem	Language	Result	Execution time	Memory
465482		MohamedFaresNebili	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	316 KiB

crocodile

#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<long long, int>>adj[n]; 
    vector<bool>exit(n, false); vector<long long>d(n, 1e10); 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); queue<int>q; 
    while(!pq.empty()) {
        int a=pq.top().second; long long w=pq.top().second; pq.pop();
        for(auto u:adj[a]) {
            int to=u.first; long long s=u.second; 
			if(queued[to]) continue; 
			if(!used[to]) { q.push(to); used[to]=true; }
			len[to].push_back(d[a]+s); income[to]++;
        }
      	if(pq.empty()) {
          while(!q.empty()) {
            	int to=q.front(); q.pop();
				if(income[to]==1) continue;
                sort(len[to].begin(), len[to].end());
                pq.push({len[to][1], to});
                queued[to]=true; d[to]=len[to][1]; 
          }
        }
    }
    return (d[0]!=1e10?d[0]:-1);
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:21:42: warning: unused variable 'w' [-Wunused-variable]
   21 |         int a=pq.top().second; long long w=pq.top().second; pq.pop();
      |                                          ^

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