Submission #787134

#	Time	Username	Problem	Language	Result	Execution time	Memory
787134		Sam_a17	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	24 ms	47188 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define ff first
#define ss second
 
ll ttt;
const ll INF=1e16;
const ll MOD=1e9+7;
const ll N=2000007;
ll n,m,k;
vector<pair<ll,ll>>g[N];
 
int travel_plan(int NN, int MM, int R[][2], int L[], int KK, int P[]){
    n=NN;
    m=MM;
    k=KK;
    for(ll i=0;i<m;i++){
        // cout<<R[i][0]<<" "<<R[i][1]<<endl;
        g[R[i][0]].push_back(make_pair(R[i][1],L[i]));
        g[R[i][1]].push_back(make_pair(R[i][0],L[i]));
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    vector<ll>mn(n+1,INF),smn(n+1,INF);
    // cout<<mn[0]<<" "<<smn[0]<<endl;
    for(ll i=0;i<k;i++){
        q.push(make_pair(0,P[i]));
        mn[P[i]]=smn[P[i]]=0;
    }
    while(!q.empty()){
        ll v=q.top().ss;
        ll w=q.top().ff;
        // cout<<v<<" "<<w<<endl;
        // cout<<mn[v]<<" "<<smn[v]<<endl<<endl;
        q.pop();
        for(pii x:g[v]){
            ll to=x.ff;
            ll dist=x.ss;
            if(mn[to]>smn[v]+dist){
                smn[to]=mn[to];
                mn[to]=smn[v]+dist;
                q.push(make_pair(smn[to],to));
            }
            else if(smn[to]>smn[v]+dist){
                smn[to]=smn[v]+dist;
                q.push(make_pair(smn[to],to));
            }
        }
    }
    return smn[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:38:12: warning: unused variable 'w' [-Wunused-variable]
   38 |         ll w=q.top().ff;
      |            ^

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