oj.uz

Submission #334317

# Submission time Handle Problem Language Result Execution time Memory
334317 2020-12-09T02:39:03 Z VROOM_VARUN Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 407 ms 28144 KB 
/*
ID: varunra2
LANG: C++
TASK: pass
*/

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define int long long

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e16
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, m;
int a, b, c, d;
vector<VII> adj;
vector<VII> dadj;  // directed
VII dst;
VI da, db, dc, dd;
vector<bool> vis;
int ret = INF;

void init() {
  adj.resize(n);
  dadj.resize(n);
  dst.resize(n);
  vis.assign(n, false);
}

VI dijk(int src) {
  VI dist(n, INF);
  vector<bool> vis(n, false);
  dist[src] = 0;
  priority_queue<PII, VII, greater<PII>> pq;
  pq.push(MP(0, src));

  while (!pq.empty()) {
    int u = pq.top().y;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (auto& x : adj[u]) {
      if (vis[x.x]) continue;
      if (dist[x.x] > dist[u] + x.y) {
        dist[x.x] = dist[u] + x.y;
        pq.push(MP(dist[x.x], x.x));
      }
    }
  }
  return dist;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  int val1 = dst[u].x;
  int val2 = dst[u].y;
  for (auto& x : dadj[u]) {
    dfs(x.x);
    dst[u].x = min(dst[u].x, dst[x.x].x);
    dst[u].y = min(dst[u].y, dst[x.x].y);
  }
  ret = min(ret, min(val1 + dst[u].y, val2 + dst[u].x));
}

int longestDAG() {
  for (int i = 0; i < n; i++) {
    dst[i] = MP(dc[i], dd[i]);
  }
  // debug(dst);
  for (int i = 0; i < n; i++) {
    dfs(i);
  }
  // debug(dst);
  return ret;
}

int32_t main() {
  // #ifndef ONLINE_JUDGE
  // freopen("pass.in", "r", stdin);
  // freopen("pass.out", "w", stdout);
  // #endif
  cin.sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> a >> b >> c >> d;

  init();

  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].PB(MP(v, w));
    adj[v].PB(MP(u, w));
  }

  // trav(x, adj) debug(x);

  a--, b--, c--, d--;

  da = dijk(a), db = dijk(b), dc = dijk(c), dd = dijk(d);

  // debug(da);
  // debug(db);
  // debug(dc);
  // debug(dd);

  int dab = da[b];
  int dcd = dc[d];

  rep(u, 0, n) {
    trav(x, adj[u]) {
      // is (u, v) satisfactory
      int v = x.x;
      int dist = x.y;
      if (dab == da[u] + db[v] + dist) dadj[u].PB(x);
    }
  }

  cout << longestDAG() << '\n';

  return 0;
}

Compilation message

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:153:7: warning: unused variable 'dcd' [-Wunused-variable]
  153 |   int dcd = dc[d];
      |       ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 27196 KB Output is correct
2 Correct 381 ms 25628 KB Output is correct
3 Correct 388 ms 27488 KB Output is correct
4 Correct 357 ms 27024 KB Output is correct
5 Correct 372 ms 25400 KB Output is correct
6 Correct 366 ms 27176 KB Output is correct
7 Correct 376 ms 25464 KB Output is correct
8 Correct 373 ms 25440 KB Output is correct
9 Correct 360 ms 26388 KB Output is correct
10 Correct 303 ms 26196 KB Output is correct
11 Correct 161 ms 20332 KB Output is correct
12 Correct 369 ms 26240 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 25860 KB Output is correct
2 Correct 387 ms 25548 KB Output is correct
3 Correct 390 ms 25564 KB Output is correct
4 Correct 386 ms 25540 KB Output is correct
5 Correct 407 ms 25756 KB Output is correct
6 Correct 371 ms 27108 KB Output is correct
7 Correct 387 ms 28144 KB Output is correct
8 Correct 394 ms 25584 KB Output is correct
9 Correct 391 ms 25568 KB Output is correct
10 Correct 390 ms 25544 KB Output is correct
11 Correct 169 ms 21612 KB Output is correct
12 Correct 370 ms 27900 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2156 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 18 ms 3948 KB Output is correct
5 Correct 9 ms 2156 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 9 ms 2156 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 27196 KB Output is correct
2 Correct 381 ms 25628 KB Output is correct
3 Correct 388 ms 27488 KB Output is correct
4 Correct 357 ms 27024 KB Output is correct
5 Correct 372 ms 25400 KB Output is correct
6 Correct 366 ms 27176 KB Output is correct
7 Correct 376 ms 25464 KB Output is correct
8 Correct 373 ms 25440 KB Output is correct
9 Correct 360 ms 26388 KB Output is correct
10 Correct 303 ms 26196 KB Output is correct
11 Correct 161 ms 20332 KB Output is correct
12 Correct 369 ms 26240 KB Output is correct
13 Correct 381 ms 25860 KB Output is correct
14 Correct 387 ms 25548 KB Output is correct
15 Correct 390 ms 25564 KB Output is correct
16 Correct 386 ms 25540 KB Output is correct
17 Correct 407 ms 25756 KB Output is correct
18 Correct 371 ms 27108 KB Output is correct
19 Correct 387 ms 28144 KB Output is correct
20 Correct 394 ms 25584 KB Output is correct
21 Correct 391 ms 25568 KB Output is correct
22 Correct 390 ms 25544 KB Output is correct
23 Correct 169 ms 21612 KB Output is correct
24 Correct 370 ms 27900 KB Output is correct
25 Correct 12 ms 2156 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 18 ms 3948 KB Output is correct
29 Correct 9 ms 2156 KB Output is correct
30 Correct 1 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 3 ms 620 KB Output is correct
33 Correct 1 ms 492 KB Output is correct
34 Correct 9 ms 2156 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Correct 1 ms 492 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 352 ms 27128 KB Output is correct
41 Correct 359 ms 26252 KB Output is correct
42 Correct 358 ms 26348 KB Output is correct
43 Correct 184 ms 22636 KB Output is correct
44 Correct 190 ms 22892 KB Output is correct
45 Correct 368 ms 28072 KB Output is correct
46 Correct 379 ms 27764 KB Output is correct
47 Correct 357 ms 27020 KB Output is correct
48 Correct 182 ms 20460 KB Output is correct
49 Correct 303 ms 26664 KB Output is correct
50 Correct 369 ms 26780 KB Output is correct
51 Correct 361 ms 28084 KB Output is correct