Submission #289707

#	Time	Username	Problem	Language	Result	Execution time	Memory
289707		b00n0rp	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1145 ms	71032 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef vector <int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef pair<int,int> pii;
#define pb push_back
#define INF 1000000000000000
#define mp make_pair
#define MOD 1000000007
#define F first
#define S second
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPD(i,n) for(int i=(n);i>=0;i--)
#define FORD(i,a,b) for(int i=(a);i>=b;i--)
#define all(v) v.begin(),v.end()
#define itr ::iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define remin(a,b) (a) = min((a),(b))
#define remax(a,b) (a) = max((a),(b))

int n,m,k;
vector<pii> adj[100005];
bool exi[100005];
int dist[100005],dist2[100005];

int dijkstra(){
    set<pii>pq;
    REP(i,n){
        if(exi[i]){
            pq.insert({0,i});
            dist[i]=dist2[i]=0;
        }
        else{
            dist[i]=dist2[i]=INF;
            pq.insert({INF,i});
        }
    }
    while(!pq.empty()){
        int u = pq.begin()->S;
        pq.erase(pq.begin());
        if(!u) return dist2[u];
        for(auto x:adj[u]){
            int v = x.F;
            int tot = dist2[u]+x.S;
            if(tot < dist[v]){
                pq.erase({dist2[v],v});
                dist2[v] = dist[v];
                dist[v] = tot;
                pq.insert({dist2[v],v});
            }
            else if(tot < dist2[v]){
                pq.erase({dist2[v],v});             
                dist2[v] = tot;
                pq.insert({dist2[v],v});
            }
        }
    }
}

signed travel_plan(signed N, signed M, signed R[][2], signed L[], signed K, signed P[]){
    n = N;
    m = M;
    k = K;
    REP(i,m){
        int u,v,w;
        u = R[i][0];
        v = R[i][1];
        w = L[i];
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    REP(i,n) exi[i] = 0;
    REP(i,k){
        int x; x = P[i];
        exi[x] = 1;
    }
    return (signed)dijkstra();
}

Compilation message (stderr)

crocodile.cpp: In function 'll dijkstra()':
crocodile.cpp:35:13: warning: control reaches end of non-void function [-Wreturn-type]
   35 |     set<pii>pq;
      |             ^~

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