Submission #1216247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216247		escobrand	Crocodile's Underground City (IOI11_crocodile)	C++17	0 / 100	3 ms	5952 KiB

crocodile

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

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,M,u,v;
const int maxn = 1e5 + 10;
const ll inf = 1e15;
typedef pair<ll,ll> pii;
vector<pii> adj[maxn];
bool e[maxn],c[maxn];
ll d[maxn][2],tmp,w;
priority_queue<ll> dp[maxn];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  
  for(i = 0;i<M;i++)
  {
    u = R[i][0];
    v = R[i][1];
    w = L[i];
    adj[u].eb({v,w});
    adj[v].eb({u,w});
  }
  
  for(i = 0;i<N;i++)d[i][0] = d[i][1] = inf;
  priority_queue<pii,vector<pii>,greater<>>q;
  for(i = 0;i<K;i++)
  {
    e[P[i]] = 1;
    d[P[i]][0] = d[P[i]][1] = 0;
    q.push({0,i});
  }
  
  while(q.size())
  {
    i = q.top().se;
    w = q.top().fi;
    q.pop();
    if(c[i])continue;
    c[i] = 1;
    for(auto k : adj[i])
    {
      ll tmp = w + k.se;
      if(d[k.fi][1] > tmp)
      {
        d[k.fi][1] = tmp;
        if(d[k.fi][0] > d[k.fi][1])swap(d[k.fi][0] , d[k.fi][1]);
        q.push({d[k.fi][1],k.fi});
      }
    }
  }
  
  return d[0][1];;
}

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