Submission #421395

#	Time	Username	Problem	Language	Result	Execution time	Memory
421395		Emin2004	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1161 ms	76876 KiB

crocodile

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

#define ll long long
#define pb push_back
#define pii pair<int, ll>
#define F first
#define S second

const int N = 100005;
const int mod = 1e9;

set<pii> s;
vector<pii> a[N];
int dis1[N], dis2[N], used[N];

void djk(){
    while(!s.empty()){
        int node = (*s.begin()).S;
        int w = (*s.begin()).F;
        s.erase(s.begin());
        used[node] = 1;
        for(pii x : a[node]){
            int i = x.F;
            int j = x.S;
            if(!used[i]){
                int ds = dis2[node] + x.S;
                if(ds < dis2[i]){
                    s.erase(s.find({dis2[i], i}));
                    if(ds <= dis1[i]){
                        dis2[i] = dis1[i];
                        dis1[i] = ds;
                    }
                    else if(ds < dis2[i]){
                        dis2[i] = ds;
                    }
                    s.insert({dis2[i], i});
                }
            }
        }
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
    for(int i = 0; i < m; i++){
        a[r[i][0]].pb({r[i][1], l[i]});
        a[r[i][1]].pb({r[i][0], l[i]});
    }
    for(int i = 0; i < n; i++){
        dis1[i] = mod;
        dis2[i] = mod;
        s.insert({mod, i});
    }
    for(int i = 0; i < k; i++){
        int x = p[i];
        dis1[x] = 0;
        dis2[x] = 0;
        s.erase(s.find({mod, x}));
        s.insert({0, x});
    }
    djk();
    return dis2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void djk()':
crocodile.cpp:26:17: warning: unused variable 'j' [-Wunused-variable]
   26 |             int j = x.S;
      |                 ^
crocodile.cpp:21:13: warning: unused variable 'w' [-Wunused-variable]
   21 |         int w = (*s.begin()).F;
      |             ^

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