Submission #246362

#	Time	Username	Problem	Language	Result	Execution time	Memory
246362		chubyxdxd	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	739 ms	87140 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define sup 1e9
#define MAX_N 50000
#define MAX_M 10000000
static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
#define pb push_back
#define sc second
#define ff first
#define INF 1e9+10;
vector<vector<pair<ll,ll>>> G;
ii dis[100010];
ll pos[100010];
int vis[100100];
int travel_plan(int N, int M,int R[][2], int L[], int K, int P[])
{
  memset(vis,-1,sizeof vis);
  G.assign(N,vector<pair<ll,ll>>());
  for(int i=0;i<M;i++){
    G[R[i][0]].pb(make_pair(R[i][1],L[i]));
    G[R[i][1]].pb(make_pair(R[i][0],L[i]));
  }
  for(int i=0;i<N;i++){
    dis[i].ff=INF;dis[i].sc=INF;
    pos[i]=INF;
  }
  priority_queue<ii,vector<ii>,greater<ii>> pq;
  for(int i=0;i<K;i++){
    ll u=P[i];
    pq.push(ii(0,u));
    dis[u].ff=0;
    dis[u].sc=0;
    pos[u]=0;
  }
  while(!pq.empty()){
    ii curr=pq.top();
    pq.pop();
    if(vis[curr.sc]==1)continue;
    vis[curr.sc]=1;
    //cout<<curr.ff<<" "<<curr.sc<<endl;
    for(int i=0;i<G[curr.sc].size();i++){
      ii v=G[curr.sc][i];
      int dist=pos[curr.sc]+v.sc;
      if(dist<=dis[v.ff].ff){
	dis[v.ff].sc=dis[v.ff].ff;
	dis[v.ff].ff=dist;
	pos[v.ff]=dis[v.ff].sc;
	pq.push(ii(pos[v.ff],v.ff));
      }
      else{
	if(dist<dis[v.ff].sc){
	  dis[v.ff].sc=dist;
	  pos[v.ff]=dist;
	  pq.push(ii(dist,v.ff));
	}
      }
    }
  }
  // cout<<dis[0].sc<<endl;
  return dis[0].sc;
}/*
inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&K));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
  for(i=0; i<K; i++)
    my_assert(1==scanf("%d",&P[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
 */

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[curr.sc].size();i++){
                 ~^~~~~~~~~~~~~~~~~~
crocodile.cpp: At global scope:
crocodile.cpp:11:12: warning: 'solution' defined but not used [-Wunused-variable]
 static int solution;
            ^~~~~~~~
crocodile.cpp:10:12: warning: 'P' defined but not used [-Wunused-variable]
 static int P[MAX_N];
            ^
crocodile.cpp:9:12: warning: 'K' defined but not used [-Wunused-variable]
 static int K;
            ^
crocodile.cpp:8:12: warning: 'L' defined but not used [-Wunused-variable]
 static int L[MAX_M];
            ^
crocodile.cpp:7:12: warning: 'R' defined but not used [-Wunused-variable]
 static int R[MAX_M][2];
            ^
crocodile.cpp:6:15: warning: 'M' defined but not used [-Wunused-variable]
 static int N, M;
               ^
crocodile.cpp:6:12: warning: 'N' defined but not used [-Wunused-variable]
 static int N, M;
            ^

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