oj.uz

Submission #367208

# Submission time Handle Problem Language Result Execution time Memory
367208 2021-02-16T15:01:19 Z piddddgy Olympic Bus (JOI20_ho_t4) C++11
5 / 100
 1000 ms 6252 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));

    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 512 KB Output is correct
4 Correct 80 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 26 ms 492 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 118 ms 620 KB Output is correct
13 Correct 38 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 63 ms 492 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 6252 KB Time limit exceeded
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 Execution timed out 1088 ms 4716 KB Time limit exceeded
4 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 512 KB Output is correct
4 Correct 80 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 26 ms 492 KB Output is correct
10 Correct 114 ms 548 KB Output is correct
11 Correct 111 ms 492 KB Output is correct
12 Correct 118 ms 620 KB Output is correct
13 Correct 38 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 63 ms 492 KB Output is correct
17 Execution timed out 1087 ms 6252 KB Time limit exceeded
18 Halted 0 ms 0 KB -