Submission #465268

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

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

int n, m, k; vector<pair<int, long long>>adj[100000];
vector<int>ex; vector<bool>e; long long d[1024][1024];
long long dfs(int v, int p)
{
    if(e[v]) return 0;
    long long best=1e9, ans=1e9; int node=-1;
    for(auto u:adj[v]) {
        int to=u.first; long long w=u.second;
        if(to==p) continue;
		long long cnt=1e9;
		for(int l=0;l<k;l++) cnt=min(cnt, d[l][to]);
        if(cnt+w<best) node=to, best=cnt+w;
    }
    for(auto u:adj[v]) {
        int to=u.first; long long w=u.second;
        if(to==p||to==node) continue;
        ans=min(ans, w+dfs(to, v));
    }
    return ans;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n=N, m=M, k=K; e.assign(n, false);
    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});
    }
    for(int l=0;l<k;l++) {
        int i=P[l]; e[i]=true; ex.push_back(i);
    }
	int cnt=0;
	for(auto u:ex) {
		for(int i=0;i<n;i++) d[cnt][i]=1e9; d[cnt][u]=0;
		priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>>pq;
        pq.push({0, u}); vector<bool>vis(n);
        while(!pq.empty()) {
            int a=pq.top().second; pq.pop();
            for(auto u:adj[a]) {
                if(d[cnt][u.first]>d[cnt][a]+u.second) {
                    d[cnt][u.first]=d[cnt][a]+u.second;
                    pq.push({d[cnt][u.first], u.first});
                }
            }
        }
        cnt++;
	}
    N=dfs(0, -1);
    return N;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:39:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   39 |   for(int i=0;i<n;i++) d[cnt][i]=1e9; d[cnt][u]=0;
      |   ^~~
crocodile.cpp:39:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |   for(int i=0;i<n;i++) d[cnt][i]=1e9; d[cnt][u]=0;
      |                                       ^

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