oj.uz

Submission #246181

# Submission time Handle Problem Language Result Execution time Memory
246181 2020-07-08T10:36:07 Z egekabas Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 6392 KB 
#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]);
    
    for(ll i = 1; i <= n; ++i) depth[i] = inf;
    createtree(1);
    dfs(1, 0);
    
    for(ll i = 0; i < m; ++i){
        ll cur = n;
        ll d = inf;
        while(cur){
            if(cur == 1){
                d = dis[1][n];
                break;
            }
            for(auto u : inc[cur])
                if(u.id != i && depth[lca(u.x, cur)] < depth[e[i].y]){
                    d = min(d, dis[cur][n]+dis[1][u.x]+u.z);
                }
            if(cur == e[i].y && prt[cur][0] == e[i].x) break;
            cur = prt[cur][0];
        }
        //cout << i << ' ' << d << '\n';
        ans[i] += d;

    }
    for(ll i = 1; i <= n; ++i){
        vis[i] = 0;
        depth[i] = inf;
        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){
        ll cur = 1;
        ll d = inf;
        while(cur){
            if(cur == n){
                d = dis[n][1];
                break;
            }
            for(auto u : inc[cur])
                if(u.id != i && depth[lca(u.x, cur)] < depth[e[i].y]){
                    d = min(d, dis[cur][1]+dis[n][u.x]+u.z);
                }
            if(cur == e[i].y && prt[cur][0] == e[i].x) break;
            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.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 896 KB Output is correct
2 Correct 17 ms 768 KB Output is correct
3 Correct 20 ms 896 KB Output is correct
4 Correct 21 ms 896 KB Output is correct
5 Incorrect 29 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 896 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Execution timed out 1093 ms 4736 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 896 KB Output is correct
2 Correct 17 ms 768 KB Output is correct
3 Correct 20 ms 896 KB Output is correct
4 Correct 21 ms 896 KB Output is correct
5 Incorrect 29 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -