Submission #246219

#	Time	Username	Problem	Language	Result	Execution time	Memory
246219		uacoder123	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1187 ms	86152 KiB

crocodile

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
vector<ii> al[150001];
ii dis[150001];
set<pair<ii,lli>> s;
void dij()
{
  while(s.size()!=0)
  {
    pair<ii,lli> v=(*s.begin());
    s.erase(s.begin());
    dis[v.S]=v.F;
    for(lli i=0;i<al[v.S].size();++i)
    {
      if(dis[al[v.S][i].F].F>al[v.S][i].S+v.F.F)
      {
        s.erase(mp(dis[al[v.S][i].F],al[v.S][i].F));
        if(al[v.S][i].S+v.F.F<dis[al[v.S][i].F].S)
          dis[al[v.S][i].F]=mp(dis[al[v.S][i].F].S,al[v.S][i].S+v.F.F);
        else
          dis[al[v.S][i].F].F=al[v.S][i].S+v.F.F;
        s.insert(mp(dis[al[v.S][i].F],al[v.S][i].F));
      }
    }
  }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  lli n=N,m=M,k=K;
  for(lli i=0;i<m;++i)
  {
    lli f=R[i][0],se=R[i][1],w=L[i];
    al[f].pb(mp(se,w));
    al[se].pb(mp(f,w));
  }
  for(lli i=0;i<=n;++i)
    dis[i]=mp(1000000000000000000,1000000000000000000);
  for(lli i=0;i<k;++i)
  {
    s.insert(mp(mp(0,0),P[i]));
    dis[P[i]]=mp(0,0);
  }
  dij();
  return(dis[0].F);
}

Compilation message (stderr)

crocodile.cpp: In function 'void dij()':
crocodile.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli i=0;i<al[v.S].size();++i)
                 ~^~~~~~~~~~~~~~~

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