oj.uz

Submission #246217

# Submission time Handle Problem Language Result Execution time Memory
246217 2020-07-08T11:20:07 Z uacoder123 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 16 ms 7552 KB 
#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[i].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

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[i].size();++i)
                 ~^~~~~~~~~~~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -