Submission #1030021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030021		Malix	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	487 ms	68896 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
  vector<pii> a(n);
  REP(i,0,m){
    a[R[i][0]].PB({R[i][1],L[i]});
    a[R[i][1]].PB({R[i][0],L[i]});
  }
  vi dist(n,inf);
  vi arr(n,0);
  priority_queue<pi,vector<pi>,greater<pi>> pq;
  REP(i,0,K){
    arr[P[i]]=1;
    dist[P[i]]=0;
    pq.push({0,P[i]});
  }
  while(!pq.empty()){
    int x=pq.top().F;
    int y=pq.top().S;
    pq.pop();
    if(arr[y]>=2)continue;
    arr[y]++;
    if(arr[y]==1)continue;
    dist[y]=x;
    for(auto u:a[y]){
      if(arr[u.F]>=2)continue;
      pq.push({dist[y]+u.S,u.F});
    }
  }
  return dist[0];
}

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