Submission #1104390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104390		M_W_13	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	537 ms	90284 KiB

crocodile

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

const ll INF = 1e18;
const int MAXN = 1e5 + 7;
vector<pair<int, ll>> graf[MAXN];
ll dl[MAXN][2];

class compare {
  public:
    bool operator() (pair<ll, int> a, pair<ll, int> b) {
      return a.first > b.first;
    }
};

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
  rep(i, MAXN) {
    rep(j, 2){ 
      dl[i][j] = INF;
    }
  }
  rep(i, m) {
    int a = R[i][0];
    int b = R[i][1];
    ll waga = L[i];
    graf[a].push_back({b, waga});
    graf[b].push_back({a, waga});
  }
  bool odwiedzone[n];
  rep(i, n) {
    odwiedzone[i] = false;
  }

  //dijkstra:
  priority_queue<pair<ll, int>, vector<pair<ll, int>>, compare> pq;
  rep(i, K) {
    dl[P[i]][0] = 0;
    dl[P[i]][1] = 0;
    pq.push({0, P[i]});
  }
  while (!pq.empty()) {
    pair<ll, int> p = pq.top();
    pq.pop();
    if (odwiedzone[p.second]) {
      continue;
    }
    // cout << "v = " << p.second << " ile = " << p.first << '\n';
    if (dl[p.second][0] < INF) {
      odwiedzone[p.second] = true;
      dl[p.second][1] = p.first;
      for (auto syn: graf[p.second]) {
        if (!odwiedzone[syn.first]) {
          pq.push({syn.second + p.first, syn.first});
        }
      }
    }
    else {
      dl[p.second][0] = p.first;
    }
  }
  return dl[0][1];
}

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