oj.uz

Submission #494784

# Submission time Handle Problem Language Result Execution time Memory
494784 2021-12-16T11:05:01 Z kamalsharmaa9 Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 398 ms 23988 KB 
//https://pastebin.com/jVURaNCJ
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N               100005
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define piii            pair<pair<int,int>,pair<int,int>>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);



}
int du[N];
int dv[N];
int ans = inf;
vector<pii>gr[N];
void dijkstra1(int node, int n, int  dist[])
{
  for (int i = 0; i <= n; i++)
    dist[i] = inf;
  dist[node] = 0;
  priority_queue<pii, vector<pii>, greater<pii>>q;
  q.push({dist[node], node});
  int val;
  while (!q.empty())
  {

    node = q.top().ss;
    val = q.top().ff;
    q.pop();
    if (dist[node] < val)
      continue;
    for (auto child : gr[node])
    {
      if (dist[child.ff] > dist[node] + child.ss)
      {
        dist[child.ff] = dist[node] + child.ss;
        q.push({dist[child.ff], child.ff});
      }

    }
  }
}
int dist[N];
int dist2[2][N];
void dijkstra2(int node, int n, int end)
{

  for (int i = 0; i <= n; i++)
  {
    dist[i] = dist2[0][i] = dist2[1][i] = inf;
  }
  dist[node] = 0;
  priority_queue<pii, vector<pii>, greater<pii>>q;
  q.push({0, node});
  dist2[0][node] = du[node];
  dist2[1][node] = dv[node];
  while (!q.empty())
  {
    node = q.top().ss;
    int val = q.top().ff;
    q.pop();
    for (auto child : gr[node])
    {
      int to_com = min( dist2[0][node], du[child.ff]) + min(dist2[1][node], dv[child.ff]);
      if (dist[child.ff] > dist[node] + child.ss)
      {
        // cout << child.ff << endl;
        dist[child.ff] = dist[node] + child.ss;
        dist2[0][child.ff] = min(dist2[0][node], du[child.ff]);
        dist2[1][child.ff] = min(dist2[1][node], dv[child.ff]);
        q.push({dist[child.ff], child.ff});
      }
      else if (dist[child.ff] == dist[node] + child.ss && dist2[0][child.ff] + dist2[1][child.ff] > to_com)
      {

        dist2[0][child.ff] = min( dist2[0][node], du[child.ff]);
        dist2[1][child.ff] = min(dist2[1][node], dv[child.ff]);
      }
    }
  }
  ans = min(ans, dist2[0][end] + dist2[1][end]);
  //cout << dist2[0][7] << " " << dist2[1][7] << " " << dist2[0][2] << " " << dist2[1][2] << endl;
}
int32_t main()
{
  c_p_c();
  int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
  for (int i = 0; i < m; i++)
  {
    int a, b, c; cin >> a >> b >> c;
    gr[a].pb({b, c});
    gr[b].pb({a, c});

  }
  dijkstra1(u, n, du);
  dijkstra1(v, n, dv);
  ans = dv[u];
  dijkstra2(s, n, t);
  dijkstra2(t, n, s);
  cout << ans << '\n';
  return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra2(long long int, long long int, long long int)':
commuter_pass.cpp:86:9: warning: unused variable 'val' [-Wunused-variable]
   86 |     int val = q.top().ff;
      |         ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 20236 KB Output is correct
2 Correct 363 ms 19032 KB Output is correct
3 Correct 359 ms 20072 KB Output is correct
4 Correct 315 ms 19108 KB Output is correct
5 Correct 313 ms 22104 KB Output is correct
6 Correct 362 ms 23988 KB Output is correct
7 Correct 349 ms 22232 KB Output is correct
8 Correct 351 ms 22368 KB Output is correct
9 Correct 341 ms 23108 KB Output is correct
10 Correct 290 ms 23164 KB Output is correct
11 Correct 145 ms 13892 KB Output is correct
12 Correct 360 ms 23080 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 19176 KB Output is correct
2 Correct 362 ms 19012 KB Output is correct
3 Correct 334 ms 18988 KB Output is correct
4 Correct 375 ms 19088 KB Output is correct
5 Correct 393 ms 19016 KB Output is correct
6 Correct 339 ms 19156 KB Output is correct
7 Correct 340 ms 18928 KB Output is correct
8 Correct 398 ms 19076 KB Output is correct
9 Correct 387 ms 19004 KB Output is correct
10 Correct 350 ms 19208 KB Output is correct
11 Correct 137 ms 11900 KB Output is correct
12 Correct 346 ms 19148 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4116 KB Output is correct
2 Correct 2 ms 2676 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 15 ms 6096 KB Output is correct
5 Correct 9 ms 4376 KB Output is correct
6 Correct 3 ms 2732 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 2 ms 2756 KB Output is correct
10 Correct 10 ms 4344 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2684 KB Output is correct
14 Correct 3 ms 2696 KB Output is correct
15 Correct 3 ms 2756 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 20236 KB Output is correct
2 Correct 363 ms 19032 KB Output is correct
3 Correct 359 ms 20072 KB Output is correct
4 Correct 315 ms 19108 KB Output is correct
5 Correct 313 ms 22104 KB Output is correct
6 Correct 362 ms 23988 KB Output is correct
7 Correct 349 ms 22232 KB Output is correct
8 Correct 351 ms 22368 KB Output is correct
9 Correct 341 ms 23108 KB Output is correct
10 Correct 290 ms 23164 KB Output is correct
11 Correct 145 ms 13892 KB Output is correct
12 Correct 360 ms 23080 KB Output is correct
13 Correct 344 ms 19176 KB Output is correct
14 Correct 362 ms 19012 KB Output is correct
15 Correct 334 ms 18988 KB Output is correct
16 Correct 375 ms 19088 KB Output is correct
17 Correct 393 ms 19016 KB Output is correct
18 Correct 339 ms 19156 KB Output is correct
19 Correct 340 ms 18928 KB Output is correct
20 Correct 398 ms 19076 KB Output is correct
21 Correct 387 ms 19004 KB Output is correct
22 Correct 350 ms 19208 KB Output is correct
23 Correct 137 ms 11900 KB Output is correct
24 Correct 346 ms 19148 KB Output is correct
25 Correct 9 ms 4116 KB Output is correct
26 Correct 2 ms 2676 KB Output is correct
27 Correct 2 ms 2692 KB Output is correct
28 Correct 15 ms 6096 KB Output is correct
29 Correct 9 ms 4376 KB Output is correct
30 Correct 3 ms 2732 KB Output is correct
31 Correct 2 ms 2892 KB Output is correct
32 Correct 3 ms 2892 KB Output is correct
33 Correct 2 ms 2756 KB Output is correct
34 Correct 10 ms 4344 KB Output is correct
35 Correct 2 ms 2636 KB Output is correct
36 Correct 2 ms 2688 KB Output is correct
37 Correct 2 ms 2684 KB Output is correct
38 Correct 3 ms 2696 KB Output is correct
39 Correct 3 ms 2756 KB Output is correct
40 Correct 313 ms 23856 KB Output is correct
41 Correct 297 ms 22916 KB Output is correct
42 Correct 322 ms 23104 KB Output is correct
43 Correct 118 ms 13892 KB Output is correct
44 Correct 136 ms 13812 KB Output is correct
45 Correct 294 ms 21960 KB Output is correct
46 Correct 286 ms 21820 KB Output is correct
47 Correct 322 ms 23716 KB Output is correct
48 Correct 111 ms 13360 KB Output is correct
49 Correct 261 ms 23460 KB Output is correct
50 Correct 300 ms 21948 KB Output is correct
51 Correct 272 ms 21816 KB Output is correct