oj.uz

Submission #1033502

# Submission time Handle Problem Language Result Execution time Memory
1033502 2024-07-25T00:14:44 Z ArthuroWich Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 3 ms 2140 KB 
#include "crocodile.h"
#include <set>
#include <vector>
#include <cstring>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
#define MAX_N 100000
 
#define trav(it, cont) for(auto it = cont.begin(); it != cont.end(); it++)
 
typedef pair<int, int> pii;
vector<vector<pii> > adj;
int visited[MAX_N];
int best[MAX_N];
int secondBest[MAX_N];
 
int travel_plan(int N, int M,int R[][2],int L[], int K, int P[]){
  //in case called again - not sure how the IOI judge would do
  adj.clear();
  adj.resize(N);
  memset(visited, 0, sizeof(visited));
  memset(best, -1, sizeof(best));
  memset(secondBest, -1, sizeof(secondBest));
  for(int i = 0; i<M; i++){
    int t = R[i][0];
    int f = R[i][1];
    adj[t].push_back(pii(f, L[i]));
    adj[f].push_back(pii(t, L[i]));
  }
  set<pii> pq;
  for(int i = 0; i<K; i++){
    pq.insert(pii(0, P[i]));
  }
  
  while(!pq.empty()){
    pii v = *(pq.begin());
    pq.erase(pq.begin());
    trav(u, adj[v.second]) {
      pii uu = *u;
      visited[uu.first]++;
      int distance = uu.second + v.first;
      if(visited[uu.first] == 1){
    best[uu.first] = distance;
      } else if(visited[uu.first] == 2){
    int lowest = min(best[uu.first], distance);
    int highest = max(best[uu.first], distance);
    best[uu.first] = lowest;
    secondBest[uu.first] = highest;
    pq.insert(pii(highest, uu.first));
      } else {
    if(distance > secondBest[uu.first]) continue;
    pq.erase(pii(secondBest[uu.first], uu.first));
    int bestX, secondBestX;
    if(distance < best[uu.first]){
      bestX = distance;
      secondBestX = best[uu.first];
    } else {
      bestX = best[uu.first];
      secondBestX = distance;
    }
    best[uu.first] = bestX;
    secondBest[uu.first] = secondBestX;
    pq.insert(pii(secondBestX, uu.first));
      }
    }
  }
  return secondBest[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1728 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1728 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 2 ms 1680 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1740 KB Output is correct
12 Correct 3 ms 1884 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Incorrect 1 ms 1468 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1728 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 2 ms 1680 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1740 KB Output is correct
12 Correct 3 ms 1884 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Incorrect 1 ms 1468 KB Output isn't correct
15 Halted 0 ms 0 KB -