oj.uz

Submission #258839

# Submission time Handle Problem Language Result Execution time Memory
258839 2020-08-06T15:36:13 Z monus1042 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 801 ms 93736 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define mkp make_pair
#define all(X) X.begin(), X.end()

const int MAXS = 100002;
const ll inf = 1e15;
vector< pair<int, ll> > g[MAXS];
priority_queue < pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll,int> > > pq;
vll d(MAXS, inf), d2(MAXS, inf);
int state[MAXS]; // 0 unvisited, 1 minimal obtained

void dj(){
  
  while(!pq.empty()){
    int auxu = pq.top().second;
    ll w = pq.top().first;
    pq.pop();
    if (state[auxu] == 0 && w == d2[auxu]){ // ok
      state[auxu] = 1;
      for (int i=0; i<(int)g[auxu].size(); i++){
	int v = g[auxu][i].first;
	ll wuv = g[auxu][i].second + w;
	if (wuv < d[v]){
	  if (d[v] < d2[v]){ // process it
	    d2[v] = d[v];
	    pq.push(mkp(d2[v], v));
	  }
	  d[v] = wuv;
	  pq.push(mkp(wuv, v));
	}else{
	  if (wuv < d2[v]){
	    d2[v] = wuv;
	    pq.push(mkp(wuv, v));
	  }
	}
      }
    }//else ignore it
  }
  
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  for (int i=0; i<M; i++){
    g[ R[i][0] ].pb(mkp( R[i][1] , L[i]));
    g[ R[i][1] ].pb(mkp( R[i][0] , L[i]));
  }

  for (int i=0; i<K; i++){
    pq.push(mkp(0, P[i]));
    d[P[i]] = d2[P[i]] = 0;
    //state[P[i]] = 1;
  }

  dj();
  return (int)d2[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 7 ms 4736 KB Output is correct
10 Correct 3 ms 4352 KB Output is correct
11 Correct 4 ms 4480 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 3 ms 4352 KB Output is correct
15 Correct 5 ms 4480 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 4 ms 4352 KB Output is correct
5 Correct 4 ms 4352 KB Output is correct
6 Correct 3 ms 4352 KB Output is correct
7 Correct 3 ms 4352 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 7 ms 4736 KB Output is correct
10 Correct 3 ms 4352 KB Output is correct
11 Correct 4 ms 4480 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 3 ms 4352 KB Output is correct
15 Correct 5 ms 4480 KB Output is correct
16 Correct 624 ms 85968 KB Output is correct
17 Correct 98 ms 18040 KB Output is correct
18 Correct 140 ms 20644 KB Output is correct
19 Correct 801 ms 93736 KB Output is correct
20 Correct 366 ms 69308 KB Output is correct
21 Correct 50 ms 11000 KB Output is correct
22 Correct 401 ms 65528 KB Output is correct