oj.uz

Submission #367217

# Submission time Handle Problem Language Result Execution time Memory
367217 2021-02-16T15:29:34 Z piddddgy Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 115 ms 5100 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;

        if(m <= 1000) {
            G[u[i]].emplace(c[i], v[i]);
        } else {
            if(i%2 == 1) {
                G[u[i]].emplace(c[i], v[i]);
            } else {
                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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 492 KB Output is correct
4 Correct 82 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 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 23 ms 620 KB Output is correct
10 Correct 114 ms 492 KB Output is correct
11 Correct 115 ms 492 KB Output is correct
12 Correct 113 ms 492 KB Output is correct
13 Correct 38 ms 640 KB Output is correct
14 Correct 54 ms 620 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 55 ms 492 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 26 ms 4076 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 38 ms 5100 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 35 ms 5100 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 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 73 ms 492 KB Output is correct
4 Correct 82 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 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 23 ms 620 KB Output is correct
10 Correct 114 ms 492 KB Output is correct
11 Correct 115 ms 492 KB Output is correct
12 Correct 113 ms 492 KB Output is correct
13 Correct 38 ms 640 KB Output is correct
14 Correct 54 ms 620 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 55 ms 492 KB Output is correct
17 Incorrect 48 ms 5100 KB Output isn't correct
18 Halted 0 ms 0 KB -