oj.uz

Submission #996458

# Submission time Handle Problem Language Result Execution time Memory
996458 2024-06-10T16:00:37 Z yellowtoad Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 395 ms 99664 KB 
#include "crocodile.h"
#include <iostream>
#include <vector>
#include <queue>
#define f first
#define s second
using namespace std;

long long dist[100010][2], vis[100010][2];
vector<pair<int,long long>> edge[100010];
priority_queue<pair<long long,pair<int,int>>,vector<pair<long long,pair<int,int>>>,greater<pair<long long,pair<int,int>>>> pq;

int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
  for (int i = 0; i < m; i++) {
    edge[R[i][0]].push_back({R[i][1],L[i]});
    edge[R[i][1]].push_back({R[i][0],L[i]});
  }
  for (int i = 0; i < n; i++) dist[i][0] = dist[i][1] = 1e18;
  for (int i = 0; i < k; i++) {
    dist[P[i]][0] = dist[P[i]][1] = 0;
    pq.push({0,{P[i],0}});
    pq.push({0,{P[i],1}});
  }
  while (pq.size()) {
    int u = pq.top().s.f, v = pq.top().s.s;
    pq.pop();
    if (vis[u][v]) continue;
    vis[u][v] = 1;
    if (!v) continue;
    for (int i = 0; i < edge[u].size(); i++) {
      if (dist[edge[u][i].f][0] > dist[u][1]+edge[u][i].s) {
        dist[edge[u][i].f][1] = dist[edge[u][i].f][0];
        dist[edge[u][i].f][0] = dist[u][1]+edge[u][i].s;
        pq.push({dist[edge[u][i].f][0],{edge[u][i].f,0}});
        pq.push({dist[edge[u][i].f][1],{edge[u][i].f,1}});
      } else if (dist[edge[u][i].f][1] > dist[u][1]+edge[u][i].s) {
        dist[edge[u][i].f][1] = dist[u][1]+edge[u][i].s;
        pq.push({dist[edge[u][i].f][1],{edge[u][i].f,1}});
      }
    }
  }
  return dist[0][1];
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < edge[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 2 ms 8832 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8932 KB Output is correct
9 Correct 3 ms 9084 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 4 ms 9308 KB Output is correct
13 Correct 3 ms 9308 KB Output is correct
14 Correct 2 ms 8820 KB Output is correct
15 Correct 3 ms 9308 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 2 ms 8832 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8932 KB Output is correct
9 Correct 3 ms 9084 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 4 ms 9308 KB Output is correct
13 Correct 3 ms 9308 KB Output is correct
14 Correct 2 ms 8820 KB Output is correct
15 Correct 3 ms 9308 KB Output is correct
16 Correct 314 ms 91080 KB Output is correct
17 Correct 93 ms 26052 KB Output is correct
18 Correct 98 ms 28360 KB Output is correct
19 Correct 395 ms 99664 KB Output is correct
20 Correct 191 ms 74832 KB Output is correct
21 Correct 34 ms 17108 KB Output is correct
22 Correct 229 ms 72432 KB Output is correct