Submission #239498

#	Time	Username	Problem	Language	Result	Execution time	Memory
239498		chubyxdxd	악어의 지하 도시 (IOI11_crocodile)	C++17	0 / 100	5 ms	640 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
vector<vector<pair<ll,ll>>> G;
ll dist[10001];
vi parent(10001, 0);
ll best[10010];
void dijkstra(ll n){
  dist[n]=0;
  priority_queue<ii,vector<ii>,greater<ii> > pq;
  pq.push(ii(0,n));
  while(!pq.empty()){
    ii front=pq.top();
    pq.pop();
    ll u=front.second,d=front.first;
    if(d>dist[u])continue;
    for(ll i=0;i<G[u].size();i++){
      ii v=G[u][i];
      if(dist[u]+v.second<dist[v.first]){
	dist[v.first]=dist[u]+v.second;
	parent[v.first]=u;
	pq.push(ii(dist[v.first],v.first));
      }
    }
  }
}
ll res;
int vis[10010];
int swich[10010];
void dfs(ll x,ll pos){
  vis[x]=1;
  if(swich[x]==1){
    res=min(res,pos);
    return;
  }
  vector<pair<pair<ll,ll>,ll>> gg;
  for(ll i=0;i<G[x].size();i++){
    gg.pb(make_pair(ii(best[G[x][i].first],G[x][i].second),G[x][i].first));
  }
  ll sw=0;
  sort(gg.begin(),gg.end());
  for(ll i=0;i<gg.size();i++){
    if(vis[gg[1].second]==-1){
      if(sw==1){
	dfs(gg[i].second,pos+gg[i].first.second);
	break;
      }
      else{
	sw=1;
      }
    }
  }
}
int travel_plan(int N, int M,int R[][2], int L[], int K, int P[])
{
  memset(swich,-1,sizeof swich);
  for(ll i=0;i<K;i++){
    swich[P[i]]=1;
  }
  res=sup;
  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(ll i=0;i<N;i++){
    memset(dist,sup,sizeof dist);
    dijkstra(i);
    ll curr=sup;
    for(ll j=0;j<K;j++){
      curr=min(curr,dist[P[i]]);
    }
    best[i]=curr;
  }
  dfs(0,0);
  return res;
}/*
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 'void dijkstra(ll)':
crocodile.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=0;i<G[u].size();i++){
                ~^~~~~~~~~~~~
crocodile.cpp: In function 'void dfs(ll, ll)':
crocodile.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=0;i<G[x].size();i++){
              ~^~~~~~~~~~~~
crocodile.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=0;i<gg.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: 0 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11