Submission #426479

#	Time	Username	Problem	Language	Result	Execution time	Memory
426479		Trickster	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	4 ms	5068 KiB

crocodile

//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
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11