oj.uz

Submission #201853

# Submission time Handle Problem Language Result Execution time Memory
201853 2020-02-12T09:07:16 Z nvmdava Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 39520 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 200002
#define MOD 1000000007

ll d[201][201];
ll ans = 0x3f3f3f3f3f3f3f3f;
int p[N];
vector<pair<pair<int, int>, ll> > road[N];
int n, m;

void update(int id, int l, int r, int L, int R, int v, int u, int c){
    if(l > R || r < L) return;
    if(L <= l && r <= R){
        road[id].push_back({{v, u}, c});
        return;
    }
    int m = (l + r) >> 1;
    update(id << 1, l, m, L, R, v, u, c);
    update(id << 1 | 1, m + 1, r, L, R, v, u, c);
}

void solve(int id, int l, int r){
    vector<pair<pair<int, int>, ll> > ch;
    while(!road[id].empty()){
        int v = road[id].back().ff.ff;
        int u = road[id].back().ff.ss;
        ll c = road[id].back().ss;
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                ll w = d[i][v] + d[u][j] + c;
                if(w < d[i][j]){
                    ch.push_back({{i, j}, d[i][j]});
                    d[i][j] = w;
                }
            }
        }
        road[id].pop_back();
    }
    if(l == r){
        ans = min(ans, d[1][n] + d[n][1] + p[l]);
    } else {
        int m = (l + r) >> 1;
        solve(id << 1, l, m);
        solve(id << 1 | 1, m + 1, r);
    }
    while(!ch.empty()){
        d[ch.back().ff.ff][ch.back().ff.ss] = ch.back().ss;
        ch.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(d, 0x3f3f, sizeof d);

    cin>>n>>m;

    for(int i = 1; i <= n; ++i)
        d[i][i] = 0;

    for(int i = 1; i <= m; ++i){
        int v, u, c;
        cin>>v>>u>>c>>p[i];
        update(1, 0, m, 0, i - 1, v, u, c);
        update(1, 0, m, i + 1, m, v, u, c);
        update(1, 0, m, i, i, u, v, c);
    }

    solve(1, 0, m);

    cout<<(ans == 0x3f3f3f3f3f3f3f3f ? -1 : ans);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 7168 KB Output is correct
2 Correct 93 ms 5652 KB Output is correct
3 Correct 464 ms 10688 KB Output is correct
4 Correct 483 ms 10944 KB Output is correct
5 Correct 21 ms 5880 KB Output is correct
6 Correct 104 ms 5928 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 8 ms 5368 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct
10 Correct 658 ms 14928 KB Output is correct
11 Correct 670 ms 15164 KB Output is correct
12 Correct 659 ms 15152 KB Output is correct
13 Correct 498 ms 8576 KB Output is correct
14 Correct 462 ms 9188 KB Output is correct
15 Correct 462 ms 9744 KB Output is correct
16 Correct 465 ms 10268 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 39520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 6512 KB Output is correct
2 Correct 97 ms 5788 KB Output is correct
3 Execution timed out 1094 ms 21612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 7168 KB Output is correct
2 Correct 93 ms 5652 KB Output is correct
3 Correct 464 ms 10688 KB Output is correct
4 Correct 483 ms 10944 KB Output is correct
5 Correct 21 ms 5880 KB Output is correct
6 Correct 104 ms 5928 KB Output is correct
7 Correct 9 ms 5368 KB Output is correct
8 Correct 8 ms 5368 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct
10 Correct 658 ms 14928 KB Output is correct
11 Correct 670 ms 15164 KB Output is correct
12 Correct 659 ms 15152 KB Output is correct
13 Correct 498 ms 8576 KB Output is correct
14 Correct 462 ms 9188 KB Output is correct
15 Correct 462 ms 9744 KB Output is correct
16 Correct 465 ms 10268 KB Output is correct
17 Execution timed out 1089 ms 39520 KB Time limit exceeded
18 Halted 0 ms 0 KB -