Submission #226563

#	Time	Username	Problem	Language	Result	Execution time	Memory
226563		a_player	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	711 ms	89576 KiB

crocodile

#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair

using namespace std;
typedef long long ll;

vector<pair<int, ll>> grafo[100002];
pair<ll, ll> dist[100002];
priority_queue<pair<ll, int>> q;
int v[100002];
bitset<100002> vis;
long long travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  for (int i = 0; i < N; i++) {
    dist[i].f = LLONG_MAX;
    dist[i].s = LLONG_MAX;
    v[i] = 0;
  }
  for (int i = 0; i < M; i++) {
    grafo[R[i][0]].push_back(mp(R[i][1], (ll)L[i]));
    grafo[R[i][1]].push_back(mp(R[i][0], (ll)L[i]));
  }
  for (int i = 0; i < K; i++) {
    int a = P[i];
    v[a] = 2;
    dist[a].f = 0;
    dist[a].s = 0;
    q.push(mp(0, a));
  }
  while (!q.empty()) {
    int co = q.top().s;
    q.pop();
    if (vis[co]) continue;
    vis[co] = 1;
    for (int i = 0; i < grafo[co].size(); i++) {
      int no = grafo[co][i].f;
      int w = grafo[co][i].s;
      if (dist[co].s + w < dist[no].f) {
        dist[no].s = dist[no].f;
        dist[no].f = dist[co].s + w;
        v[no] += 1;
        if (v[no] >= 2) q.push(mp(-dist[no].s, no));
      } else if (dist[co].s + w < dist[no].s) {
        dist[no].s = dist[co].s + w;
        v[no] += 1;
        if (v[no] >= 2) q.push(mp(-dist[no].s, no));
      }
    }
  }
  return dist[0].s;
}

Compilation message (stderr)

crocodile.cpp: In function 'long long int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < grafo[co].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~

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