Submission #952239

#	Time	Username	Problem	Language	Result	Execution time	Memory
952239		emad234	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	426 ms	85964 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
vector<vector<pii>> v;
ll dist[mxN], mn[mxN],mnid[mxN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  v.clear();
  v.resize(N + 3);
  for (ll i = 0; i < N; i++)
  {
    dist[i] = 1e18 + 5;
    mn[i] = 1e18 + 5;
  }
  for (ll i = 0; i < M; i++)
  {
    v[R[i][1]].push_back({R[i][0], L[i]});
    v[R[i][0]].push_back({R[i][1], L[i]});
  }
  priority_queue<pii, vector<pii>, greater<pii>> q;
  for (ll i = 0; i < K; i++)
  {
    mn[P[i]] = 0;
    dist[P[i]] = 0;
    q.push({0, P[i]});
  }
  while (q.size())
  {
    auto u = q.top();
    q.pop();
    if (dist[u.S] < u.F)
      continue;
    for (auto x : v[u.S])
    {
      if (dist[x.F] > x.S + u.F && (mn[x.F] == 1e18 + 5 || mnid[x.F] == u.S))
      {
        mn[x.F] = min(x.S + u.F,mn[x.F]);
        mnid[x.F] = u.S;
      }
      else if (dist[x.F] > x.S + u.F && (mn[x.F] != 1e18 + 5 && mnid[x.F] != u.S))
      {
        ll Mn = mn[x.F];
        if(Mn > x.S + u.F){
          mn[x.F] = x.S + u.F;
          mnid[x.F] = u.S;
          dist[x.F] = Mn; 
        }else{
          dist[x.F] = x.S + u.F;
        }
        q.push({dist[x.F], x.F});
      }
    }
  }
  return dist[0];
}

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