제출 #246182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246182		egekabas	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	56 ms	6396 KiB

ho_t4

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
const ll inf = 1e18;
struct edge{
    ll x, y, z, d, id;
};
edge e[50009];
ll n, m;
ll dis[209][209];
vector<ll> g[209];
ll vis[209];
ll used[50009];
ll prt[209][10];
ll depth[209];
void createtree(ll root){
    vis[root] = 1;
    for(int i = 0; i < m; ++i)
        if(vis[e[i].y] == 0 && dis[root][e[i].y] == dis[root][e[i].x] + e[i].z){
            used[i] = 1;
            vis[e[i].y] = 1;
            g[e[i].x].pb(e[i].y);
        }
}
void dfs(ll v, ll p){
    prt[v][0] = p;
    depth[v] = depth[p]+1;
    for(ll i = 1; i < 10; ++i)
        prt[v][i] = prt[prt[v][i-1]][i-1];
    for(auto u : g[v])
        dfs(u, v);
}
int lca(ll x, ll y){
    if(depth[y] > depth[x]) swap(x, y);
    for(ll i = 9; i >= 0; --i)
        if(depth[prt[x][i]] >= depth[y])
            x = prt[x][i];
    if(x == y) return x;
    for(ll i = 9; i >= 0; --i)
        if(prt[x][i] != prt[y][i]){
            x = prt[x][i];
            y = prt[y][i];
        }
    return prt[x][0];
}
void addto(pll x, set<pll> &s){
    auto it = s.lower_bound(x);
    if(it != s.begin()){
        --it;
        if((*it).ss <= x.ss)
            return;
    }
    s.insert(x);
    while(1){
        it = s.upper_bound(x);
        if(it == s.end() || (*it).ss < x.ss) break;
        s.erase(it);
    }
}
ll ans[50009];
set<pll> alt[209];
vector<edge> inc[209];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    //freopen("in.txt", "r", stdin);                                                                                             
    //freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(ll i = 1; i <= n; ++i)
        for(ll j = 1; j <= n; ++j)
            if(i != j)
                dis[i][j] = inf;
    for(ll i = 0; i < m; ++i){
        cin >> e[i].x >> e[i].y >> e[i].z >> e[i].d;
        e[i].id = i;
        dis[e[i].x][e[i].y] = min(dis[e[i].x][e[i].y], e[i].z);
        ans[i] = e[i].d;
        inc[e[i].y].pb(e[i]);
    }
    for(ll k = 1; k <= n; ++k)
        for(ll i = 1; i <= n; ++i)
            for(ll j = 1; j <= n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
    
    createtree(1);
    dfs(1, 0);
    for(ll i = 0; i < m; ++i){
        if(used[i] == 1) continue;
        addto({depth[lca(e[i].x, e[i].y)], dis[1][e[i].x]} ,alt[e[i].y]);
    }
    for(ll i = 0; i < m; ++i){
        if(used[i] == 0){
            ans[i] += min(dis[1][n], dis[1][e[i].y] + e[i].z + dis[e[i].x][n]);
            continue;
        }
        ll cur = n;
        ll d = inf;
        while(cur){
            if(cur == 1){
                d = dis[1][n];
                break;
            }
            if(cur == e[i].y){
                for(auto u : inc[cur])
                    if(u.id != i && depth[lca(u.x, cur)] != 0 && depth[lca(u.x, cur)] < depth[e[i].y]){
                        d = min(d, dis[cur][n]+dis[1][u.x]+u.z);
                    }
                break;
            }
            auto it = alt[cur].lower_bound({depth[e[i].y], 0});
            if(it != alt[cur].begin()){
                --it;
                d = min(d, (*it).ss + dis[cur][n]);
            }
            cur = prt[cur][0];
        }
        //cout << i << ' ' << d << '\n';
        ans[i] += d;

    }
    for(ll i = 1; i <= n; ++i){
        depth[i] = vis[i] = 0;
        for(ll j = 0; j < 10; ++j)
            prt[i][j] = 0;
        g[i].clear();
        alt[i].clear();
    }
    for(ll i = 0; i < m; ++i) used[i] = 0;

    createtree(n);
    dfs(n, 0);
    for(ll i = 0; i < m; ++i){
        if(used[i] == 1) continue;
        addto({depth[lca(e[i].x, e[i].y)], dis[n][e[i].x]} ,alt[e[i].y]);
    }
    for(ll i = 0; i < m; ++i){
        if(used[i] == 0){
            ans[i] += min(dis[n][1], dis[n][e[i].y] + e[i].z + dis[e[i].x][1]);
            continue;
        }
        ll cur = 1;
        ll d = inf;
        while(cur){
            if(cur == n){
                d = dis[n][1];
                break;
            }
            if(cur == e[i].y){
                for(auto u : inc[cur])
                    if(u.id != i && depth[lca(u.x, cur)] != 0 && depth[lca(u.x, cur)] < depth[e[i].y]){
                        d = min(d, dis[cur][1]+dis[n][u.x]+u.z);
                    }
                break;
            }
            auto it = alt[cur].lower_bound({depth[e[i].y], 0});
            if(it != alt[cur].begin()){
                --it;
                d = min(d, (*it).ss + dis[cur][1]);
            }
            cur = prt[cur][0];
        }
        ans[i] += d;
    }

    ll fin = dis[1][n]+dis[n][1];
    for(ll i = 0; i < m; ++i){
        fin = min(fin, ans[i]);
    }
    if(fin >= inf)
        cout << -1;
    else
        cout << fin;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63