Submission #1197568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197568		SonicML	Crocodile's Underground City (IOI11_crocodile)	C++20	0 / 100	2 ms	2888 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

typedef long long ll;

ll const INF = 1e15;

struct Edge{
  int to;
  ll cost;
};

int const NMAX = 1e5;
vector <Edge> g[1 + NMAX];
ll dist1[1 + NMAX];
ll dist2[1 + NMAX];
int start[1 + NMAX];
int isQueue[1 + NMAX];

void computeBellman(int n, int k) {
  for(int i = 1;i <= n;i++) {
    dist1[i] = dist2[i] = INF;
  }
  queue <int> q;
  for(int i = 1;i <= k;i++) {
    dist1[start[i]] = dist2[start[i]] = 0;
    q.push(start[i]);
    isQueue[start[i]] = true;
  }
  while(!q.empty()) {
    int from = q.front();
    q.pop();
    isQueue[from] = false;
    //cerr << from << ' ' << dist1[from] << ' ' << dist2[from] << '\n';
    for(int i = 0;i < g[from].size();i++) {
      int to = g[from][i].to;
      ll newDist = dist2[from] + g[from][i].cost;
      //cerr << "  " << from << " - " << to << ' ' << dist1[to] << ' ' << dist2[to] << ' ' << newDist << '\n';
      if(newDist < dist1[to]) {
        dist2[to] = dist1[to];
	dist1[to] = newDist;
	if(!isQueue[to]) {
          isQueue[to] = true;
	  q.push(to);
        }
      }else if(newDist < dist2[to]) {
	dist2[to] = newDist;
	if(!isQueue[to]) {
	  isQueue[to] = true;
	  q.push(to);
	}
      }
    }
  }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  for(int i = 1;i <= M;i++) {
    int a = R[i-1][0], b = R[i-1][1], c = L[i-1];
    a++;
    b++;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  for(int i = 1;i <= K;i++) {
    start[i] = P[i-1]+1;
  }
  computeBellman(N, K);
  return dist2[1];
}

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