oj.uz

Submission #974983

# Submission time Handle Problem Language Result Execution time Memory
974983 2024-05-04T08:57:20 Z berr Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 132 ms 9740 KB 
    #include <bits/stdc++.h>
    using namespace std; 
    #define int long long
    const int N=205, INF=1e16;


    signed main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int n, m; cin >> n >> m;
        vector<vector<array<int, 3>>> g(n), g_rev(n);
        vector<array<int, 3>> e(m);
        vector<int> di(m);

        vector<int> all[n][n];
        int cnt =0;
        
        for(auto &[u, v, c]: e){
            cin >> u >> v >> c >> di[cnt];
            u--; v--;
            g[u].push_back({v, c, cnt});
            g_rev[v].push_back({u, c, cnt});
            all[u][v].push_back(cnt);

            cnt++;
        }
        for(int i=0; i<n; i++){
            for(int l=0; l<n; l++){
                sort(all[i][l].begin(), all[i][l].end(), [&](int x, int y){
                    return e[x][2] < e[y][2];
                });
            }
        }

        // a = 1 -> i, b = i -> n
        // c = i -> 1 without x
        // d = n -> i without x

        vector a(n+1, vector(n, INF)), b(n+1, vector(n, INF));
        vector c(n+1, vector(n, INF)), d(n+1, vector(n, INF));
        auto dijkstra=[&](int v, int skip, auto& dist, auto&&g){
            dist[v] = 0;
            priority_queue<array<int, 2>> pq;
            pq.push({0, v});

            while(pq.size()){
                auto [cost, v]=pq.top();
                pq.pop(); cost*=-1;
                if(v==skip||dist[v] != cost) continue;

                for(auto [i, l, j]: g[v]){
                    if(dist[i] > cost+l){
                        dist[i] = cost+l;
                        pq.push({-dist[i], i});
                    }
                }
            }
        };


        for(int i=0; i<=n; i++){
            dijkstra(0, i, a[i], g);
            dijkstra(n-1, i, b[i], g_rev);
            dijkstra(0, i, c[i], g_rev);
            dijkstra(n-1, i, d[i], g);
        }

        int ans=INF;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                //blocklanan edge i ve j arasında

                // 0 -> i // swap j -> n
                //
                if(a[j][i]==INF||b[i][j]==INF) continue;
                int sum=a[j][i]+b[i][j];

                for(auto k: all[j][i]){
                    sum+=e[k][2];
                    sum+=di[k];

                    ans=min(ans, sum+min((i==0)?INF:d[i][0], (j==0)?INF:d[j][0]));
                    if(all[j][i].size()>1){
                        if(k==all[j][i][0])
                            ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][1]][2]);
                        else 
                            ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][0]][2]);
                    }
                }            

            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                //blocklanan edge i ve j arasında

                if(d[j][i]==INF||c[i][j]==INF) continue;
                int sum=d[j][i]+c[i][j];

                for(auto k: all[j][i]){
                    sum+=e[k][2];
                    sum+=di[k];

                    ans=min(ans, sum+min((i==0)?INF:b[i][0], (j==0)?INF:b[j][0]));
                   
                    if(all[j][i].size()>1){
                        if(k==all[j][i][0])
                            ans=min(ans, sum+b[i][j]+a[j][i]+e[all[j][i][1]][2]);
                        else 
                            ans=min(ans, sum+b[i][j]+a[j][i]+e[all[j][i][0]][2]);
                    }
                }            

            }
        }
        ans = min(ans, a[n][n-1]+d[n][0]);
        if(ans==INF) cout<<-1;
        else cout<<ans;
    }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 21 ms 2836 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8284 KB Output is correct
2 Incorrect 126 ms 8216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 54 ms 7088 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 77 ms 8208 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 36 ms 9740 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 21 ms 2836 KB Output is correct
4 Correct 22 ms 2652 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -