oj.uz

Submission #924797

# Submission time Handle Problem Language Result Execution time Memory
924797 2024-02-09T16:58:22 Z yeediot Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 205 ms 6732 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[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;
        if(from[p][v]!=-1)used[from[p][v]]=1;
        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});
                from[p][u]=id;
            }
        }
    }
}
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(used[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[0][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:42:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         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:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         auto [dist,v]=pq.top();
      |              ^
ho_t4.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto [u,id]:adj2[v]){
      |                  ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         auto [a,b,c,d]=e[i];
      |              ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 18 ms 604 KB Output is correct
4 Correct 20 ms 600 KB Output is correct
5 Correct 2 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 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 14 ms 600 KB Output is correct
11 Correct 17 ms 600 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Incorrect 4 ms 600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 5836 KB Output is correct
2 Correct 205 ms 6364 KB Output is correct
3 Correct 184 ms 5836 KB Output is correct
4 Correct 16 ms 604 KB Output is correct
5 Incorrect 7 ms 604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 151 ms 5072 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 190 ms 5716 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 62 ms 6732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 18 ms 604 KB Output is correct
4 Correct 20 ms 600 KB Output is correct
5 Correct 2 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 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 14 ms 600 KB Output is correct
11 Correct 17 ms 600 KB Output is correct
12 Correct 17 ms 604 KB Output is correct
13 Incorrect 4 ms 600 KB Output isn't correct
14 Halted 0 ms 0 KB -