oj.uz

Submission #924789

# Submission time Handle Problem Language Result Execution time Memory
924789 2024-02-09T16:49:52 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 8020 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
struct edge{
    int a,b,c,d;
};
const int mxn=405;
const int inf=1e15;
vector<edge>e;
int from[5][mxn];
int dis[5][mxn];
vector<pii>adj[2][mxn];
vector<pii>adj2[mxn];
bool used[5][500005];
int n;
void dij(int st,int p,int type){
    for(int i=0;i<mxn;i++){
        dis[p][i]=inf;
        from[p][i]=-1;
    }
    dis[p][st]=0;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,st});
    while(sz(pq)){
        auto [dist,v]=pq.top();
        pq.pop();
        if(dist>dis[p][v])continue;
        for(auto [u,id]:adj[type][v]){
            int w=e[id].c;
            if(dist+w<dis[p][u]){
                dis[p][u]=dist+w;
                pq.push({dis[p][u],u});
                if(from[p][u]!=-1){
                    used[p][from[p][u]]=0;
                    continue;
                }
                from[p][u]=u;
                used[p][id]=1;
            }
        }
    }
}
int dij2(int st,int ed,int p,int i){
    for(int i=0;i<mxn;i++){
        dis[p][i]=inf;
        from[p][i]=inf;
    }
    dis[p][st]=0;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,st});
    while(sz(pq)){
        auto [dist,v]=pq.top();
        pq.pop();
        if(dist>dis[p][v])continue;
        for(auto [u,id]:adj2[v]){
            if(id==i and e[id].a==v)continue;
            int w=e[id].c;
            if(dist+w<dis[p][u]){
                dis[p][u]=dist+w;
                pq.push({dis[p][u],u});
            }
        }
    }
    return dis[p][ed];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        e.pb({a,b,c,d});
        adj[0][a].pb({b,i});
        adj2[a].pb({b,i});
        adj[1][b].pb({a,i});
    }
    dij(1,0,0);
    dij(1,1,1);
    dij(n,2,0);
    dij(n,3,1);
    int ans=dis[0][n]+dis[2][1];
    for(int i=0;i<m;i++){
        auto [a,b,c,d]=e[i];
        if(1 or used[0][i] or used[1][i] or used[2][i] or used[3][i]){
            e[i].c+=d;
            adj2[b].pb({a,i});
            ans=min(ans,dij2(1,n,4,i)+dij2(n,1,4,i));
            adj2[b].pop_back();
            e[i].c-=d;
        }
        else{
            ans=min(ans,min(dis[0][n],dis[3][b]+c+dis[2][a])+min(dis[2][1],dis[2][b]+dis[1][a]+c)+d);
        }
    }
    if(ans>=(int)1e15){
        cout<<-1<<'\n';
        return 0;
    }
    cout<<ans<<'\n';
}
/*
*/

Compilation message

ho_t4.cpp: In function 'void dij(long long int, long long int, long long int)':
ho_t4.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |         auto [dist,v]=pq.top();
      |              ^
ho_t4.cpp:41:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for(auto [u,id]:adj[type][v]){
      |                  ^
ho_t4.cpp: In function 'long long int dij2(long long int, long long int, long long int, long long int)':
ho_t4.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         auto [dist,v]=pq.top();
      |              ^
ho_t4.cpp:68:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |         for(auto [u,id]:adj2[v]){
      |                  ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:99:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |         auto [a,b,c,d]=e[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 33 ms 2708 KB Output is correct
4 Correct 37 ms 2704 KB Output is correct
5 Correct 9 ms 2904 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 59 ms 2652 KB Output is correct
11 Correct 55 ms 2652 KB Output is correct
12 Correct 58 ms 2652 KB Output is correct
13 Incorrect 17 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Execution timed out 1089 ms 6404 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 33 ms 2708 KB Output is correct
4 Correct 37 ms 2704 KB Output is correct
5 Correct 9 ms 2904 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 59 ms 2652 KB Output is correct
11 Correct 55 ms 2652 KB Output is correct
12 Correct 58 ms 2652 KB Output is correct
13 Incorrect 17 ms 2652 KB Output isn't correct
14 Halted 0 ms 0 KB -