oj.uz

Submission #198556

# Submission time Handle Problem Language Result Execution time Memory
198556 2020-01-26T15:14:34 Z alexandra_udristoiu Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1226 ms 61048 KB 
#include "crocodile.h"
#include<iostream>
#include<vector>
#include<set>
#define DIM 100005
#define f first
#define s second
using namespace std;
static int viz[DIM];
static pair<int, int> d[DIM];
static vector< pair<int, int> > v[DIM];
static set< pair<int, int> > h;
int travel_plan(int n, int m, int r[][2], int L[], int k, int p[]){
    int i, nod, ii, vecin;
    set< pair<int, int> > :: iterator it;
    for(i = 1; i <= n; i++){
        d[i].f = d[i].s = 1000000000;
    }
    for(i = 0; i < k; i++){
        p[i]++;
        d[ p[i] ] = make_pair(0, 0);
    }
    for(i = 0; i < m; i++){
        r[i][0]++; r[i][1]++;
        v[ r[i][0] ].push_back( make_pair(r[i][1], L[i]) );
        v[ r[i][1] ].push_back( make_pair(r[i][0], L[i]) );
    }
    d[0].s = 1000000001;
    for(i = 1; i <= n; i++){
        h.insert( make_pair(d[i].s, i) );
    }
    for(ii = 1; ii <= n; ii++){
        it = h.begin();
        nod = it->s;
        h.erase(it);
        viz[nod] = 1;
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i].f;
            if(d[vecin].f > d[nod].s + v[nod][i].s){
                h.erase( make_pair(d[vecin].s, vecin) );
                d[vecin].s = d[vecin].f;
                d[vecin].f = d[nod].s + v[nod][i].s;
                h.insert( make_pair(d[vecin].s, vecin) );
            }
            else{
                if(d[vecin].s > d[nod].s + v[nod][i].s){
                    h.erase( make_pair(d[vecin].s, vecin) );
                    d[vecin].s = d[nod].s + v[nod][i].s;
                    h.insert( make_pair(d[vecin].s, vecin) );
                }
            }
        }
    }
    return d[1].s;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 9 ms 2896 KB Output is correct
10 Correct 7 ms 2684 KB Output is correct
11 Correct 8 ms 2808 KB Output is correct
12 Correct 11 ms 3064 KB Output is correct
13 Correct 11 ms 3192 KB Output is correct
14 Correct 7 ms 2680 KB Output is correct
15 Correct 8 ms 2808 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Correct 7 ms 2680 KB Output is correct
4 Correct 8 ms 2808 KB Output is correct
5 Correct 7 ms 2808 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 9 ms 2896 KB Output is correct
10 Correct 7 ms 2684 KB Output is correct
11 Correct 8 ms 2808 KB Output is correct
12 Correct 11 ms 3064 KB Output is correct
13 Correct 11 ms 3192 KB Output is correct
14 Correct 7 ms 2680 KB Output is correct
15 Correct 8 ms 2808 KB Output is correct
16 Correct 764 ms 40056 KB Output is correct
17 Correct 161 ms 18552 KB Output is correct
18 Correct 222 ms 19448 KB Output is correct
19 Correct 1226 ms 61048 KB Output is correct
20 Correct 359 ms 49760 KB Output is correct
21 Correct 74 ms 9208 KB Output is correct
22 Correct 421 ms 47408 KB Output is correct