Submission #781137

#	Time	Username	Problem	Language	Result	Execution time	Memory
781137		I_Love_EliskaM_	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	688 ms	75444 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second

const int N=1e5+55;
vector<pi> adj[N];
int ok[N];
int d[N];
int vis[N];

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {

  forn(i,m) {
    int u=r[i][0], v=r[i][1], w=l[i];
    adj[u].pb({v,w}), adj[v].pb({u,w});
  }

  priority_queue<pi> q;
  forn(i,k) q.push({0,p[i]}), vis[p[i]]=1;

  while (q.size()) {
    auto it=q.top(); q.pop();
    int di=-it.f, u=it.s;
    ++vis[u];
    if (vis[u]!=2) continue;
    d[u]=di;
    for(auto&e:adj[u]) {
      int v=e.f, w=e.s;
      q.push({-di-w,v});
    }
  }
  return d[0];

}

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