oj.uz

Submission #426482

# Submission time Handle Problem Language Result Execution time Memory
426482 2021-06-14T05:11:09 Z Trickster Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 807 ms 94672 KB 
//Suleyman Atayew

#include "crocodile.h"
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set> 
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 50000
#define MAX_M 10000000
#define maxN 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <ll, ll>
#define sz(a) (ll)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

ll n, m, k;
ll vis[maxN], dis[maxN][5];
vector <pii> E[maxN];
priority_queue <pii> Q;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N, m = M, k = K;

    for(ll i = 0; i < m; i++) {
        ll a = R[i][0], b = R[i][1], c = L[i];

        E[a].pb({b, c});
        E[b].pb({a, c});
    }
    
    for(ll i = 0; i < n; i++) dis[i][0] = dis[i][1] = 1e15;

    for(ll i = 0; i < k; i++) {
        ll x = P[i];

        Q.push({0, x});
        vis[x] = 1, dis[x][0] = dis[x][1] = 0;
    }

    while(!Q.empty()) {
        ll nd = Q.top().ss;
        Q.pop();

        if(vis[nd] == 2) continue;

        vis[nd]++;

        if(vis[nd] == 1) continue;
        for(auto i: E[nd]) {
            ll to = i.ff;
            ll w = i.ss;

            if(vis[to] == 2) continue;

            if(dis[to][0] > dis[nd][1]+w) {
                dis[to][1] = dis[to][0];
                dis[to][0] = dis[nd][1]+w;
                Q.push({-dis[to][0], to});
            }
            else if(dis[to][1] > dis[nd][1]+w) {
                dis[to][1] = dis[nd][1]+w;
                Q.push({-dis[to][1], to});
            }
        }
    }

    return dis[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5144 KB Output is correct
8 Correct 4 ms 5132 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5144 KB Output is correct
8 Correct 4 ms 5132 KB Output is correct
9 Correct 6 ms 5396 KB Output is correct
10 Correct 4 ms 5004 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 7 ms 5708 KB Output is correct
13 Correct 7 ms 5836 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 4 ms 5144 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5144 KB Output is correct
8 Correct 4 ms 5132 KB Output is correct
9 Correct 6 ms 5396 KB Output is correct
10 Correct 4 ms 5004 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 7 ms 5708 KB Output is correct
13 Correct 7 ms 5836 KB Output is correct
14 Correct 4 ms 5068 KB Output is correct
15 Correct 4 ms 5068 KB Output is correct
16 Correct 562 ms 88720 KB Output is correct
17 Correct 91 ms 23060 KB Output is correct
18 Correct 152 ms 25600 KB Output is correct
19 Correct 807 ms 94672 KB Output is correct
20 Correct 318 ms 70472 KB Output is correct
21 Correct 46 ms 13016 KB Output is correct
22 Correct 343 ms 67416 KB Output is correct