oj.uz

답안 #202703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202703 2020-02-17T20:24:51 Z osaaateiasavtnl Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 63 ms 29032 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1e5 + 7, INF = 1e18 + 7;
struct Edge {
    int u, v, c, d;
} e[N];  
 
struct Ed {
    int v, c, i;
};  
 
int n, m;
int dist1[N], par1[N], par_ed1[N], sec1[N], best1[N];
int distn[N], parn[N], par_edn[N], secn[N], bestn[N];
int tmp[N];
int dist1_rev[N], sec1_rev[N], best1_rev[N];;
int distn_rev[N], secn_rev[N], bestn_rev[N];

vector <Ed> g[N], gr[N];
int get1n(int u, int v) {
    return dist1[u] + distn_rev[v];
}
int getn1(int u, int v) {
    return distn[u] + dist1_rev[v];
}   
int get1n(int i) {
    return get1n(e[i].u, e[i].v) + e[i].c;
}   
int getn1(int i) {
    return getn1(e[i].u, e[i].v) + e[i].c;
}   

void dj(int S, int *dist, vector <Ed> g[N], int par[N], int par_ed[N], int sec[N], int best[N]) {
    for (int i = 0; i < N; ++i) {
        dist[i] = INF;
        best[i] = -1;
        sec[i] = INF;
    }
    set <ii> ms;
    dist[S] = 0;
    ms.insert(mp(0, S));
    while (ms.size()) {
        int u = ms.begin()->s;
        ms.erase(ms.begin());
        for (auto e : g[u]) {
            if (dist[u] + e.c < dist[e.v]) {
                ms.erase(mp(dist[e.v], e.v));
                sec[e.v] = dist[e.v];
                dist[e.v] = dist[u] + e.c;  

                par[e.v] = u;
                par_ed[e.v] = e.i;

                best[e.v] = e.i;
                ms.insert(mp(dist[e.v], e.v));
            }   
            else {
                sec[e.v] = min(sec[e.v], dist[u] + e.c);
            }   
        }   
    }   
}
 
int from1(int u, int ban) {
    if (ban != best1[u])
        return dist1[u];
    else
        return sec1[u];
}   
int ton(int u, int ban) {
    if (ban != bestn_rev[u])
        return distn_rev[u];
    else
        return secn_rev[u];
}   
int fromn(int u, int ban) {
    if (ban != bestn[u])
        return distn[u];
    else
        return secn[u];
}
int to1(int u, int ban) {
    if (ban != best1_rev[u])
        return dist1_rev[u];
    else
        return sec1_rev[u];
}   
 
int dist1n_del[N], distn1_del[N];
vector <int> tree[N], add[N], del[N];
bool used[N];
const int LG = 20;
int to[N][LG], tin[N], tout[N], timer = 0;
void dfs1(int u, int p) {
    to[u][0] = p;
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i - 1]][i - 1];
    tin[u] = timer++;
    for (int v : tree[u])
        dfs1(v, u);
    tout[u] = timer++;              
}   
bool anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}   
int lca(int u, int v) {
    if (anc(u, v))
        return u;
    for (int i = LG - 1; i >= 0; --i)
        if (!anc(to[u][i], v))
            u = to[u][i];
    return to[u][0];
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].c >> e[i].d;
        g[e[i].u].app({e[i].v, e[i].c, i});
        gr[e[i].v].app({e[i].u, e[i].c, i});
    }
    dj(1, dist1, g, par1, par_ed1, sec1, best1); 
    dj(n, distn, g, parn, par_edn, secn, bestn); 
    dj(1, dist1_rev, gr, tmp, tmp, sec1_rev, best1_rev); 
    dj(n, distn_rev, gr, tmp, tmp, secn_rev, bestn_rev);

    for (int i = 2; i <= n; ++i) 
        if (par1[i]) {
            tree[par1[i]].app(i);
            used[par_ed1[i]] = 1;
        }   
    dfs1(1, 1);
    for (int i = 0; i < m; ++i) {
        if (anc(e[i].v, e[i].u))
            continue;
        if (!used[i]) {
            int l = lca(e[i].u, e[i].v);
            int x = get1n(i);
            if (anc(l, n)) {
                if (anc(e[i].u, n) && !anc(e[i].u, e[i].v)) {
                    add[e[i].u].app(x);
                    del[l].app(x);                        
                }   
                else if (anc(e[i].v, n)) {
                    add[e[i].v].app(x);
                    del[l].app(x);
                }   
            }   
        }   
    }

    if (!par1[n]) {
        for (int i = 0; i < N; ++i)
            dist1n_del[i] = INF;
    }
    else {
        for (int i = 0; i < N; ++i)
            dist1n_del[i] = dist1[n];
        int u = n;
        multiset <int> ms = {INF};
        while (u != 1) {
            //cout << "up " << u << '\n';
            for (int e : add[u]) {
                ms.insert(e);
                //cout << "insert " << e << '\n';
            }
            for (int e : del[u]) {
                ms.erase(ms.find(e));   
                //cout << "erase " << e << '\n';
            }
            dist1n_del[par_ed1[u]] = *ms.begin();
            u = to[u][0];
        }   
    }    

    for (int i = 0; i < N; ++i) {
        tree[i].clear();
        add[i].clear();
        del[i].clear();
    }            
    memset(used, 0, sizeof used);            
    for (int i = 1; i < n; ++i)
        if (parn[i]) {
            tree[parn[i]].app(i);
            used[par_edn[i]] = 1;
        }   

    dfs1(n, n);
    for (int i = 0; i < m; ++i) {
        if (anc(e[i].v, e[i].u))
            continue;
        if (!used[i]) {
            int l = lca(e[i].u, e[i].v);
            int x = getn1(i);
            if (anc(l, 1)) {                
                if (anc(e[i].u, 1) && !anc(e[i].u, e[i].v)) {
                    add[e[i].u].app(x);
                    del[l].app(x);                        
                }   
                else if (anc(e[i].v, 1)) {
                    add[e[i].v].app(x);
                    del[l].app(x);
                }   
            }   
        }   
    }           
    if (!parn[1]) {
        for (int i = 0; i < N; ++i)
            distn1_del[i] = INF;
    }   
    else {
        for (int i = 0; i < N; ++i)
            distn1_del[i] = distn[1];
        int u = 1;
        multiset <int> ms = {INF};
        while (u != n) {
            for (int e : add[u])
                ms.insert(e);
            for (int e : del[u])
                ms.erase(ms.find(e));
            distn1_del[par_edn[u]] = *ms.begin();
            u = to[u][0];
        }   
    }   
    
    #ifdef HOME
    for (int i = 0; i < m; ++i)
        cout << dist1n_del[i] << ' ';
    cout << '\n';
    for (int i = 0; i < m; ++i)
        cout << distn1_del[i] << ' ';
    cout << '\n';
    #endif

    int ans = dist1[n] + distn[1];
    for (int i = 0; i < m; ++i) {
        int d1n = from1(e[i].v, i) + ton(e[i].u, i) + e[i].c;
        int dn1 = fromn(e[i].v, i) + to1(e[i].u, i) + e[i].c;
        d1n = min(d1n, dist1n_del[i]);
        dn1 = min(dn1, distn1_del[i]);        
        ans = min(ans, d1n + dn1 + e[i].d);
    }
    if (ans > 1e12)
        cout << "-1\n";
    else 
        cout << ans << '\n';
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23292 KB Output is correct
2 Correct 19 ms 23292 KB Output is correct
3 Correct 20 ms 23416 KB Output is correct
4 Correct 20 ms 23416 KB Output is correct
5 Correct 20 ms 23288 KB Output is correct
6 Correct 19 ms 23288 KB Output is correct
7 Correct 19 ms 23160 KB Output is correct
8 Correct 23 ms 23160 KB Output is correct
9 Correct 22 ms 23288 KB Output is correct
10 Correct 20 ms 23416 KB Output is correct
11 Correct 20 ms 23416 KB Output is correct
12 Correct 20 ms 23416 KB Output is correct
13 Correct 19 ms 23292 KB Output is correct
14 Incorrect 21 ms 23416 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 28664 KB Output is correct
2 Correct 62 ms 28328 KB Output is correct
3 Correct 61 ms 28280 KB Output is correct
4 Correct 21 ms 23416 KB Output is correct
5 Correct 20 ms 23288 KB Output is correct
6 Correct 21 ms 23288 KB Output is correct
7 Correct 19 ms 23160 KB Output is correct
8 Correct 19 ms 23160 KB Output is correct
9 Correct 59 ms 29032 KB Output is correct
10 Correct 57 ms 28660 KB Output is correct
11 Correct 58 ms 28664 KB Output is correct
12 Correct 59 ms 28664 KB Output is correct
13 Correct 57 ms 28664 KB Output is correct
14 Correct 56 ms 28664 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 23416 KB Output is correct
2 Correct 20 ms 23288 KB Output is correct
3 Correct 49 ms 27128 KB Output is correct
4 Correct 20 ms 23288 KB Output is correct
5 Correct 57 ms 28152 KB Output is correct
6 Correct 19 ms 23164 KB Output is correct
7 Correct 19 ms 23160 KB Output is correct
8 Correct 53 ms 28920 KB Output is correct
9 Correct 54 ms 28896 KB Output is correct
10 Incorrect 59 ms 28156 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23292 KB Output is correct
2 Correct 19 ms 23292 KB Output is correct
3 Correct 20 ms 23416 KB Output is correct
4 Correct 20 ms 23416 KB Output is correct
5 Correct 20 ms 23288 KB Output is correct
6 Correct 19 ms 23288 KB Output is correct
7 Correct 19 ms 23160 KB Output is correct
8 Correct 23 ms 23160 KB Output is correct
9 Correct 22 ms 23288 KB Output is correct
10 Correct 20 ms 23416 KB Output is correct
11 Correct 20 ms 23416 KB Output is correct
12 Correct 20 ms 23416 KB Output is correct
13 Correct 19 ms 23292 KB Output is correct
14 Incorrect 21 ms 23416 KB Output isn't correct
15 Halted 0 ms 0 KB -