oj.uz

Submission #1069041

# Submission time Handle Problem Language Result Execution time Memory
1069041 2024-08-21T15:07:46 Z DeathIsAwe Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 678 ms 82196 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
bool visited[100000];
pair<int,int> dist[100000];


class compare {
  public: bool operator()(vector<int> a, vector<int> b) {
    if (a[0] == b[0]) {
      if (a[1] == b[1]) {
        return a[2] > b[2];
      }
      return a[1] > b[1];
    }
    return a[0] > b[0];
  }
};


int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
  vector<vector<pair<int,int>>> graph(100000);
  for (int i=0;i<m;i++) {
    graph[r[i][0]].push_back(make_pair(r[i][1], l[i]));
    graph[r[i][1]].push_back(make_pair(r[i][0], l[i]));
  }
  for (int i=0;i<100000;i++) {
    visited[i] = false;
    dist[i].first = INT_MAX;
    dist[i].second = INT_MAX;
  }


  priority_queue<vector<int>, vector<vector<int>>, compare> pq;
  vector<int> dum(3), top(3);
  for (int i=0;i<k;i++) {
    dum[0] = 0; dum[1] = 0; dum[2] = p[i];
    pq.push(dum);
    dist[p[i]].first = 0; dist[p[i]].second = 0;
  }
  

  int bruh;
  while (pq.size() > 0) {
    top = pq.top(); pq.pop();
    //cout << top[0] << ' ' << top[1] << ' ' << top[2] << '\n';
    if (visited[top[2]]) {continue;}
    visited[top[2]] = true;
    for (pair<int,int> i: graph[top[2]]) {
      if (!visited[i.first]) {
        bruh = i.second + top[0];
        if (bruh < dist[i.first].second) {
          dist[i.first].first = dist[i.first].second;
          dist[i.first].second = bruh;
          dum[0] = dist[i.first].first; dum[1] = dist[i.first].second; dum[2] = i.first;
          pq.push(dum);
        } else  if (bruh < dist[i.first].first) {
          dist[i.first].first = bruh;
          dum[0] = dist[i.first].first; dum[1] = dist[i.first].second; dum[2] = i.first;
          pq.push(dum);
        }
      }
    }
  }


  //for (int i=0;i<n;i++) {
  //  cout << dist[i].first << ' ' << dist[i].second << '\n';
  //}
  return dist[0].first;
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7120 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7132 KB Output is correct
12 Correct 4 ms 7512 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7004 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 3 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7120 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 3 ms 7132 KB Output is correct
12 Correct 4 ms 7512 KB Output is correct
13 Correct 3 ms 7512 KB Output is correct
14 Correct 2 ms 7004 KB Output is correct
15 Correct 2 ms 7260 KB Output is correct
16 Correct 399 ms 68240 KB Output is correct
17 Correct 191 ms 22484 KB Output is correct
18 Correct 210 ms 23556 KB Output is correct
19 Correct 678 ms 82196 KB Output is correct
20 Correct 163 ms 54608 KB Output is correct
21 Correct 68 ms 12300 KB Output is correct
22 Correct 284 ms 51556 KB Output is correct