oj.uz

Submission #367221

# Submission time Handle Problem Language Result Execution time Memory
367221 2021-02-16T15:33:08 Z piddddgy Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 113 ms 10220 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});
            }
        }
    }
    
    if(m > 1000 and dis[y] != 1e18) {
        assert(dis[y] == 0);
    }
    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 49 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 72 ms 492 KB Output is correct
4 Correct 80 ms 492 KB Output is correct
5 Correct 63 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 0 ms 364 KB Output is correct
9 Correct 23 ms 620 KB Output is correct
10 Correct 113 ms 492 KB Output is correct
11 Correct 110 ms 492 KB Output is correct
12 Correct 109 ms 492 KB Output is correct
13 Correct 36 ms 492 KB Output is correct
14 Correct 53 ms 492 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 53 ms 620 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 10220 KB Execution killed with signal 6
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 28 ms 4076 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 36 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 36 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 49 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 72 ms 492 KB Output is correct
4 Correct 80 ms 492 KB Output is correct
5 Correct 63 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 0 ms 364 KB Output is correct
9 Correct 23 ms 620 KB Output is correct
10 Correct 113 ms 492 KB Output is correct
11 Correct 110 ms 492 KB Output is correct
12 Correct 109 ms 492 KB Output is correct
13 Correct 36 ms 492 KB Output is correct
14 Correct 53 ms 492 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 53 ms 620 KB Output is correct
17 Runtime error 51 ms 10220 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -