oj.uz

Submission #367215

# Submission time Handle Problem Language Result Execution time Memory
367215 2021-02-16T15:25:07 Z piddddgy Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 115 ms 8300 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;
#define cerr if(false) cerr
#define watch(x) cerr << (#x) << " is " << (x) << endl;
#define endl '\n'
#define ld long double
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
    
const int maxn = 250;
const int maxm = 50500;
    
int n, m;
int u[maxm], v[maxm], c[maxm], d[maxm];
int dis[maxn];
    
// .fi = cost, .se = destination
multiset<pii> G[maxn];
    
int dist(int x, int y) {
    cerr << "go from " << x << " -> " << y << endl;
    for(int i = 1; i <= n; i++) {
        dis[i] = 1e18;
    }
    watch(sz(G[2]))
    
    priority_queue<pii> pq;
    dis[x] = 0;
    pq.push({0, x});
    
    while(!pq.empty()) {
        pii S = pq.top(); pq.pop();
        cerr << "on " << S.se << endl;
    
        S.fi *= -1;
    
        for(pii e: G[S.se]) {
            cerr << "edge " << e.fi << " " << e.se << endl;
            if(dis[e.se] > S.fi+e.fi) {
                cerr << "pushing " << e.se << endl;
                dis[e.se] = S.fi+e.fi;
                pq.push({-dis[e.se], e.se});
            }
        }
    }
    
    return dis[y];
}
    
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> c[i] >> d[i];
    
        cerr << "going from " << u[i] << " to " << v[i] << " w cost " << c[i] << endl;
        G[u[i]].emplace(c[i], v[i]);

        if(m > 1000) {
            G[v[i]].emplace(c[i], u[i]);
        }
    }
    
    watch(sz(G[2]))
    // watch(ree)
    int ans = 1e18;
    ans = min(ans, dist(1, n)+dist(n, 1));

    if(m <= 1000)
    for(int i = 1; i <= m; i++) {
        cerr << "trying " << i << endl;
        // reverse
        G[u[i]].erase(G[u[i]].lower_bound({c[i], v[i]}));
        G[v[i]].emplace(c[i], u[i]);
    
        int to = dist(1, n);
        int back = dist(n, 1);
    
        watch(to)
        watch(back)
        ans = min(ans, d[i] + to + back);
        // put back
        G[v[i]].erase(G[v[i]].lower_bound({c[i], u[i]}));
        G[u[i]].emplace(c[i], v[i]);
        cerr << endl;
    }
    
    if(ans == 1e18) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}
    
/*
    
simulate inverting each edge
    
4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5
-> 10
    
4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5
-> 10
    
4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
-> 2
    
4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5
-> 12
    
4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5
-> -1
    
Did you read the bounds?
Did you make typos?
Are there edge cases (N=1?)
Are array sizes proper?
Integer overflow?
DS reset properly between test cases?
Is using long longs causing TLE?
Are you using floating points?
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 492 KB Output is correct
4 Correct 81 ms 492 KB Output is correct
5 Correct 62 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 23 ms 492 KB Output is correct
10 Correct 115 ms 492 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 113 ms 492 KB Output is correct
13 Correct 36 ms 492 KB Output is correct
14 Correct 54 ms 492 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 53 ms 492 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 8300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 45 ms 6508 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 72 ms 8172 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 69 ms 8172 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 492 KB Output is correct
4 Correct 81 ms 492 KB Output is correct
5 Correct 62 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 23 ms 492 KB Output is correct
10 Correct 115 ms 492 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 113 ms 492 KB Output is correct
13 Correct 36 ms 492 KB Output is correct
14 Correct 54 ms 492 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 53 ms 492 KB Output is correct
17 Incorrect 82 ms 8300 KB Output isn't correct
18 Halted 0 ms 0 KB -