oj.uz

Submission #421395

# Submission time Handle Problem Language Result Execution time Memory
421395 2021-06-09T06:37:52 Z Emin2004 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1161 ms 76876 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2832 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 3 ms 2660 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 3 ms 2660 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 3 ms 2832 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 5 ms 3404 KB Output is correct
14 Correct 3 ms 2660 KB Output is correct
15 Correct 3 ms 2764 KB Output is correct
16 Correct 732 ms 71860 KB Output is correct
17 Correct 154 ms 23460 KB Output is correct
18 Correct 217 ms 25100 KB Output is correct
19 Correct 1161 ms 76876 KB Output is correct
20 Correct 320 ms 62720 KB Output is correct
21 Correct 66 ms 11460 KB Output is correct
22 Correct 383 ms 59100 KB Output is correct