oj.uz

Submission #234774

# Submission time Handle Problem Language Result Execution time Memory
234774 2020-05-25T14:06:49 Z muhammad_hokimiyon Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 953 ms 59972 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double long

using namespace std;

const int NN = 2e6 + 7;
const int maxn = 1e5 + 7;
//const int M = 22;
const int mod = 998244353;
const ll inf = 1e18 + 7;
const dl rf = 1e-14;
const int B = sqrt(maxn);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int b[maxn];
bool used[maxn];
vector < pair < int , int > > v[maxn];
vector < int > d(maxn , 2e9);
vector < int > d1(maxn , 2e9);

int travel_plan(int n, int m, int a[][2], int l[], int k, int p[])
{
    for( int i = 0; i < m; i++ ){
        a[i][0] += 1 , a[i][1] += 1;
    }
    for( int i = 0; i < m; i++ ){
        v[a[i][0]].push_back({ a[i][1] , l[i] });
        v[a[i][1]].push_back({ a[i][0] , l[i] });
    }
    set < pair < int , int > > s;
    for( int i = 0; i < k; i++ ){
        p[i] += 1;
        d[p[i]] = 0;
        d1[p[i]] = 0;
        s.insert({ 0 , p[i] });
    }
    while( !s.empty() ){
        auto x = *s.begin();
        s.erase(s.begin());
        for( auto y : v[x.se] ){
            if( d[y.fi] >= y.se + d1[x.se] ){
                s.erase({ d1[y.fi] , y.fi });
                d1[y.fi] = d[y.fi];
                d[y.fi] = y.se + d1[x.se];
                if( d1[y.fi] != 2e9 )s.insert({ d1[y.fi] , y.fi });
            }else{
                if( d1[y.fi] > y.se + d1[x.se] ){
                    s.erase({ d1[y.fi] , y.fi });
                    d1[y.fi] = y.se + d1[x.se];
                    s.insert({ d1[y.fi] , y.fi });
                }
            }
        }
    }
    return d1[1];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 9 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 10 ms 4096 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3456 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3584 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3584 KB Output is correct
8 Correct 7 ms 3584 KB Output is correct
9 Correct 9 ms 3712 KB Output is correct
10 Correct 6 ms 3456 KB Output is correct
11 Correct 8 ms 3584 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct
13 Correct 10 ms 4096 KB Output is correct
14 Correct 7 ms 3584 KB Output is correct
15 Correct 7 ms 3584 KB Output is correct
16 Correct 661 ms 56568 KB Output is correct
17 Correct 103 ms 13816 KB Output is correct
18 Correct 130 ms 15480 KB Output is correct
19 Correct 953 ms 59972 KB Output is correct
20 Correct 350 ms 50512 KB Output is correct
21 Correct 55 ms 8312 KB Output is correct
22 Correct 390 ms 46456 KB Output is correct