oj.uz

Submission #426479

# Submission time Handle Problem Language Result Execution time Memory
426479 2021-06-14T04:56:05 Z Trickster Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 4 ms 5068 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][1], 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
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 Incorrect 4 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 4 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 Incorrect 4 ms 5068 KB Output isn't correct
5 Halted 0 ms 0 KB -