oj.uz

Submission #246362

# Submission time Handle Problem Language Result Execution time Memory
246362 2020-07-08T22:35:19 Z chubyxdxd Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 739 ms 87140 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 6 ms 768 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct
12 Correct 12 ms 1536 KB Output is correct
13 Correct 8 ms 1536 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 896 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 5 ms 896 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 7 ms 1152 KB Output is correct
10 Correct 6 ms 768 KB Output is correct
11 Correct 6 ms 1024 KB Output is correct
12 Correct 12 ms 1536 KB Output is correct
13 Correct 8 ms 1536 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 896 KB Output is correct
16 Correct 575 ms 76836 KB Output is correct
17 Correct 117 ms 20976 KB Output is correct
18 Correct 152 ms 23536 KB Output is correct
19 Correct 739 ms 87140 KB Output is correct
20 Correct 360 ms 61976 KB Output is correct
21 Correct 54 ms 9464 KB Output is correct
22 Correct 379 ms 58252 KB Output is correct