Submission #201853

#	Time	Username	Problem	Language	Result	Execution time	Memory
201853		nvmdava	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1094 ms	39520 KiB

ho_t4

#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 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63