oj.uz

Submission #445827

# Submission time Handle Problem Language Result Execution time Memory
445827 2021-07-19T19:37:53 Z stat0r1c Commuter Pass (JOI18_commuter_pass) C++11
100 / 100
 373 ms 25564 KB 
#include <bits/stdc++.h>
/* #include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> */
using namespace std;
// using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned ll;
template<typename T> using vt = vector<T>;
using vi = vt<int>;
using vvi = vt<vi>;
using ii = pair<int, int>;
using vii = vt<ii>;
/* template<typename T>
using indexed_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; */
/* struct chash {
    static ull hash_f(ull x) {x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);}
    size_t operator()(ull x) const {static const ull RANDOM = chrono::steady_clock::now().time_since_epoch().count();return hash_f(x + RANDOM);}
};
struct iihash {
    template <class T1, class T2>
    size_t operator () (const pair<T1,T2> &p) const {auto h1 = hash<T1>{}(p.first);auto h2 = hash<T2>{}(p.second);return h1 ^ h2;}
};
template<class T1, class T2, class T3> using ii_umap = gp_hash_table<pair<T1,T2>,T3,iihash>;
template<class T1, class T2> using f_umap = gp_hash_table<T1,T2,chash>;
template<class T1, class T2> using o_umap = gp_hash_table<T1,T2>; */
#define sqr(x) (x)*(x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define debug(x) cerr << #x << " -> " << x << '\n'
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int inf = 1e9 + 7;
const ll infll = 1e18 + 10;
template <typename T> inline T fgcd(T a, T b) {while(b) swap(b, a %= b); return a;}
ll fpow(ll a, ll b) {ll o = 1; for(;b;b >>= 1) {if(b & 1) o = o * a;a = a * a;} return o;}
ll fpow(ll a, ll b, ll m) {ll o = 1; a %= m; for(;b;b >>= 1) {if(b & 1) o = o * a % m;a = a * a % m;} return o;}
template<class T> void uniq(vt<T> &a) {sort(all(a));a.resize(unique(all(a)) - a.begin());}
const int N = 1e5;
using pli = pair<ll, int>;
int n,m,s,t,u,v,x,y,z;
vii a[N + 1];
vi ts,ed[N + 1],vis(N + 1);
void dfs(int uu) {
    vis[uu] = 1;
    for(int e : ed[uu]) if(!vis[e]) dfs(e);
    ts.pb(uu);
}
void dijkstra(int st, vt<ll> &d) {
    priority_queue<pli, vt<pli>, greater<pli>> pq;
    pq.push({0,st});
    d.assign(n + 1, infll);
    d[st] = 0;
    while(!pq.empty()) {
        ll du = pq.top().F;
        int uu = pq.top().S;
        pq.pop();
        if(d[uu] != du) continue;
        for(ii e : a[uu]) {
            if(d[e.S] > du + e.F) pq.push({d[e.S] = du + e.F, e.S});
        }
    }
}
int main() {
    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
    while(m--) {
        scanf("%d%d%d", &x, &y, &z);
        a[x].eb(z,y);
        a[y].eb(z,x);
    }
    vt<ll> b,d,e,h;
    dijkstra(s, b);
    dijkstra(u, d);
    dijkstra(v, e);
    dijkstra(t, h);
    for(int i = 1; i <= n; i++) {
        for(ii g : a[i]) {
            if(b[t] == b[i] + h[g.S] + g.F) {
                ed[i].pb(g.S);
            }
        }
    }
    dfs(s);
    reverse(all(ts));
    ll ans = d[v];
    vt<ll> minu(n + 1, infll), minv(n + 1, infll);
    for(int i : ts) {
        minu[i] = min(minu[i], d[i]);
        minv[i] = min(minv[i], e[i]);
        for(int j : ed[i]) {
            minu[j] = min(minu[j], minu[i]);
            minv[j] = min(minv[j], minv[i]);
        }
        ans = min(ans, min(minu[i] + e[i], minv[i] + d[i]));
    }
    printf("%lld", ans);
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d%d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19804 KB Output is correct
2 Correct 318 ms 18996 KB Output is correct
3 Correct 327 ms 25564 KB Output is correct
4 Correct 288 ms 20876 KB Output is correct
5 Correct 306 ms 21428 KB Output is correct
6 Correct 307 ms 21792 KB Output is correct
7 Correct 322 ms 21836 KB Output is correct
8 Correct 339 ms 21432 KB Output is correct
9 Correct 289 ms 20896 KB Output is correct
10 Correct 245 ms 20792 KB Output is correct
11 Correct 115 ms 18728 KB Output is correct
12 Correct 315 ms 20724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 20148 KB Output is correct
2 Correct 325 ms 20460 KB Output is correct
3 Correct 361 ms 19960 KB Output is correct
4 Correct 359 ms 20288 KB Output is correct
5 Correct 343 ms 21176 KB Output is correct
6 Correct 325 ms 22864 KB Output is correct
7 Correct 342 ms 23688 KB Output is correct
8 Correct 327 ms 20480 KB Output is correct
9 Correct 323 ms 21208 KB Output is correct
10 Correct 333 ms 20060 KB Output is correct
11 Correct 159 ms 20344 KB Output is correct
12 Correct 332 ms 23420 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6476 KB Output is correct
2 Correct 4 ms 5324 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 19 ms 7452 KB Output is correct
5 Correct 12 ms 6404 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 5 ms 5412 KB Output is correct
8 Correct 5 ms 5580 KB Output is correct
9 Correct 4 ms 5452 KB Output is correct
10 Correct 11 ms 6432 KB Output is correct
11 Correct 3 ms 5324 KB Output is correct
12 Correct 3 ms 5324 KB Output is correct
13 Correct 3 ms 5324 KB Output is correct
14 Correct 4 ms 5452 KB Output is correct
15 Correct 4 ms 5452 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 19804 KB Output is correct
2 Correct 318 ms 18996 KB Output is correct
3 Correct 327 ms 25564 KB Output is correct
4 Correct 288 ms 20876 KB Output is correct
5 Correct 306 ms 21428 KB Output is correct
6 Correct 307 ms 21792 KB Output is correct
7 Correct 322 ms 21836 KB Output is correct
8 Correct 339 ms 21432 KB Output is correct
9 Correct 289 ms 20896 KB Output is correct
10 Correct 245 ms 20792 KB Output is correct
11 Correct 115 ms 18728 KB Output is correct
12 Correct 315 ms 20724 KB Output is correct
13 Correct 373 ms 20148 KB Output is correct
14 Correct 325 ms 20460 KB Output is correct
15 Correct 361 ms 19960 KB Output is correct
16 Correct 359 ms 20288 KB Output is correct
17 Correct 343 ms 21176 KB Output is correct
18 Correct 325 ms 22864 KB Output is correct
19 Correct 342 ms 23688 KB Output is correct
20 Correct 327 ms 20480 KB Output is correct
21 Correct 323 ms 21208 KB Output is correct
22 Correct 333 ms 20060 KB Output is correct
23 Correct 159 ms 20344 KB Output is correct
24 Correct 332 ms 23420 KB Output is correct
25 Correct 12 ms 6476 KB Output is correct
26 Correct 4 ms 5324 KB Output is correct
27 Correct 3 ms 5324 KB Output is correct
28 Correct 19 ms 7452 KB Output is correct
29 Correct 12 ms 6404 KB Output is correct
30 Correct 5 ms 5452 KB Output is correct
31 Correct 5 ms 5412 KB Output is correct
32 Correct 5 ms 5580 KB Output is correct
33 Correct 4 ms 5452 KB Output is correct
34 Correct 11 ms 6432 KB Output is correct
35 Correct 3 ms 5324 KB Output is correct
36 Correct 3 ms 5324 KB Output is correct
37 Correct 3 ms 5324 KB Output is correct
38 Correct 4 ms 5452 KB Output is correct
39 Correct 4 ms 5452 KB Output is correct
40 Correct 294 ms 22312 KB Output is correct
41 Correct 295 ms 20844 KB Output is correct
42 Correct 298 ms 20932 KB Output is correct
43 Correct 131 ms 21308 KB Output is correct
44 Correct 136 ms 21296 KB Output is correct
45 Correct 298 ms 23292 KB Output is correct
46 Correct 291 ms 23220 KB Output is correct
47 Correct 286 ms 21644 KB Output is correct
48 Correct 166 ms 19164 KB Output is correct
49 Correct 300 ms 21712 KB Output is correct
50 Correct 288 ms 22536 KB Output is correct
51 Correct 292 ms 23476 KB Output is correct