oj.uz

Submission #1024902

# Submission time Handle Problem Language Result Execution time Memory
1024902 2024-07-16T12:04:28 Z mindiyak Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 326 ms 69056 KB 
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<long long> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;

#include "crocodile.h"

vector<vpi> paths(1e5+6,vpi());

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  FOR(i,0,M){
    paths[R[i][0]].pb({R[i][1],L[i]});
    paths[R[i][1]].pb({R[i][0],L[i]});
  }

  vi visited(N,0);
  vl dist1(N,1e18);
  vl dist2(N,1e18);

  priority_queue<pair<ll,int>> pq;
  FOR(i,0,K){
    pq.push({0,P[i]});
    dist1[P[i]] = 0;
    dist2[P[i]] = 0;
  }

  while(!pq.empty()){
    int node = pq.top().S;
    ll dist = pq.top().F;
    pq.pop();
    // cout << node << " " << dist << endl;
    if(visited[node])continue;
    visited[node] = 1;
    for(auto edge:paths[node]){
      ll temp = -dist + edge.S;
      if(dist1[edge.F] > temp){
        dist2[edge.F] = dist1[edge.F];
        dist1[edge.F] = temp;
        pq.push({-dist2[edge.F],edge.F});
      }
      else if(dist2[edge.F] > temp){
        dist2[edge.F] = temp;
        pq.push({-dist2[edge.F],edge.F});
      }
    }
  }

  // FOR(i,0,N){
  //   cout << i << " " << dist[i] << endl;
  // }

  return dist2[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6920 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 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6920 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 3 ms 7168 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6920 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 3 ms 7168 KB Output is correct
13 Correct 3 ms 7260 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 237 ms 62144 KB Output is correct
17 Correct 63 ms 18904 KB Output is correct
18 Correct 69 ms 20308 KB Output is correct
19 Correct 326 ms 69056 KB Output is correct
20 Correct 163 ms 50260 KB Output is correct
21 Correct 26 ms 11748 KB Output is correct
22 Correct 194 ms 48724 KB Output is correct