oj.uz

Submission #964606

# Submission time Handle Problem Language Result Execution time Memory
964606 2024-04-17T07:49:35 Z onebit1024 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 6476 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(c) c.begin(), c.end()
#define endl "\n"

const double PI=3.141592653589;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "LINE(" << __LINE__ << ") -> " <<"[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

int n,m;
vector<set<pair<int,int>>>adj;
const int inf = 1e18;
int dij(int u, int v){
    vector<int>dist(n+1,inf);
    dist[u] = 0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    pq.push({0,u});
    while(!pq.empty()){
        int u = pq.top().second, d = pq.top().first;
        pq.pop();
        if(d!=dist[u])continue;
        for(auto &[v,c] : adj[u]){
            if(dist[u] +c < dist[v]){
                dist[v] = dist[u]+c;
                pq.push({dist[v],v});
            }
        }
    }
    return dist[v];
}

void solve()
{
    cin >> n >> m;
    adj = vector<set<pair<int,int>>>(n+1);
    vector<vector<int>>edges;
    for(int i = 1;i<=m;++i){
        int u,v,c,d;cin >> u >> v >> c >> d;
        adj[u].insert({v,c});
        edges.pb({u,v,c,d});
    }

    int res = min(inf,dij(1,n)+dij(n,1));
    for(auto x : edges){
        int u = x[0], v = x[1], c = x[2], d = x[3];
        adj[u].erase({v,c});
        adj[v].insert({u,c});
        res = min(res, dij(1,n) + dij(n,1)+d);
        adj[u].insert({v,c});
        adj[v].erase({u,c});
    }
    if(res==inf)res = -1;
    cout << res << endl;
}   

int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    

    int T=1;
    for(int i = 1;i<=T;++i)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 612 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 44 ms 612 KB Output is correct
4 Correct 49 ms 612 KB Output is correct
5 Correct 17 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 15 ms 612 KB Output is correct
10 Correct 71 ms 604 KB Output is correct
11 Correct 74 ms 600 KB Output is correct
12 Correct 72 ms 600 KB Output is correct
13 Correct 22 ms 600 KB Output is correct
14 Correct 32 ms 600 KB Output is correct
15 Correct 28 ms 604 KB Output is correct
16 Correct 27 ms 600 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Execution timed out 1079 ms 5652 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 612 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 44 ms 612 KB Output is correct
4 Correct 49 ms 612 KB Output is correct
5 Correct 17 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 15 ms 612 KB Output is correct
10 Correct 71 ms 604 KB Output is correct
11 Correct 74 ms 600 KB Output is correct
12 Correct 72 ms 600 KB Output is correct
13 Correct 22 ms 600 KB Output is correct
14 Correct 32 ms 600 KB Output is correct
15 Correct 28 ms 604 KB Output is correct
16 Correct 27 ms 600 KB Output is correct
17 Execution timed out 1070 ms 6476 KB Time limit exceeded
18 Halted 0 ms 0 KB -