oj.uz

Submission #367214

# Submission time Handle Problem Language Result Execution time Memory
367214 2021-02-16T15:24:10 Z piddddgy Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 113 ms 6124 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]);
    }
    
    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 50 ms 652 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 620 KB Output is correct
4 Correct 80 ms 512 KB Output is correct
5 Correct 61 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 23 ms 492 KB Output is correct
10 Correct 113 ms 492 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 110 ms 620 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 Correct 49 ms 5100 KB Output is correct
2 Incorrect 39 ms 6124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 25 ms 4204 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 37 ms 5996 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 36 ms 5996 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 652 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 620 KB Output is correct
4 Correct 80 ms 512 KB Output is correct
5 Correct 61 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 23 ms 492 KB Output is correct
10 Correct 113 ms 492 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 110 ms 620 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 Correct 49 ms 5100 KB Output is correct
18 Incorrect 39 ms 6124 KB Output isn't correct
19 Halted 0 ms 0 KB -