Submission #788520

#	Time	Username	Problem	Language	Result	Execution time	Memory
788520		acatmeowmeow	Crocodile's Underground City (IOI11_crocodile)	C++11	46 / 100	3 ms	2900 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
int dist[NMAX + 5][2];
vector<pair<int, int>> adj[NMAX + 5];
bool vis[NMAX + 5];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < M; i++) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }

    for (int i = 0; i < N; i++) dist[i][0] = dist[i][1] = 1e9, vis[i] = false;

    for (int i = 0; i < K; i++) dist[P[i]][1] = 0, pq.push({0, P[i]});

    while (pq.size()) {
        int p = pq.top().first, u = pq.top().second; pq.pop();
        if (p > dist[u][1]) continue;
        for (auto&x : adj[u]) {
            int v = x.first, c = x.second, prevDist = dist[v][1];
			vector<int> cur = {dist[v][0], dist[v][1], p + c};
			sort(cur.begin(), cur.end());
			dist[v][0] = cur[0], dist[v][1] = cur[1];
			if (prevDist != dist[v][1]) pq.push({dist[v][1], v});
        }
    }
    //for (int i = 0; i < N; i++) cout << dist[i][0] << " ";
    return dist[0][1];
}

/*#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  //my_assert(3==scanf("%d %d %d",&N,&M,&K));
  cin >> N>> M >> K;
  for(i=0; i<M; i++)
    //my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
    cin >> R[i][0] >> R[i][1] >> L[i];
  for(i=0; i<K; i++)
    //my_assert(1==scanf("%d",&P[i]));
    cin >> P[i];
  //my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
cout << ans << '\n';

  return 0;
}*/

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11