oj.uz

Submission #711180

# Submission time Handle Problem Language Result Execution time Memory
711180 2023-03-16T09:28:07 Z JJAnawat Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 327 ms 24544 KB 
#include<bits/stdc++.h>

#define int long long
#define F first
#define S second

using namespace std;
using pi=pair<int,int>;

const int inf=1e18;
int n,m;
int S,T,U,V;
vector<pi> g[100005];

vector<int> dijk(int s){
    vector<int> dis(n+1,inf);
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    dis[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto [du,u]=pq.top();
        pq.pop();
        if(du!=dis[u])
            continue;
        for(auto [v,w]:g[u]){
            if(dis[v]>du+w){
                dis[v]=du+w;
                pq.push({du+w,v});
            }
        }
    }
    return dis;
}

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

    cin >> n >> m >> S >> T >> U >> V;
    for(int i=0,a,b,c;i<m;i++){
        cin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    vector<int> s=dijk(S),t=dijk(T),u=dijk(U),v=dijk(V);
    vector<int> dpu(n+1,inf),dpv(n+1,inf);
    vector<pi> vec;
    for(int i=1;i<=n;i++){
        if(s[i]+t[i]==s[T])
            vec.push_back({s[i],i});
    }
    sort(vec.begin(),vec.end());
    int ans=inf;
    for(auto [si,i]:vec){
        dpu[i]=u[i];
        dpv[i]=v[i];
        for(auto [j,w]:g[i]){
            if(s[j]+w+t[i]==s[T]){
                dpu[i]=min(dpu[i],dpu[j]);
                dpv[i]=min(dpv[i],dpv[j]);
            }
        }
        ans=min(ans,dpu[i]+v[i]);
        ans=min(ans,dpv[i]+u[i]);
    }
    ans=min(ans,u[V]);
    cout << ans;
}

Compilation message

commuter_pass.cpp: In function 'std::vector<long long int> dijk(long long int)':
commuter_pass.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         auto [du,u]=pq.top();
      |              ^
commuter_pass.cpp:25:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         for(auto [v,w]:g[u]){
      |                  ^
commuter_pass.cpp: At global scope:
commuter_pass.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main(){
      | ^~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto [si,i]:vec){
      |              ^
commuter_pass.cpp:57:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for(auto [j,w]:g[i]){
      |                  ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 23316 KB Output is correct
2 Correct 282 ms 22236 KB Output is correct
3 Correct 300 ms 24544 KB Output is correct
4 Correct 263 ms 23048 KB Output is correct
5 Correct 273 ms 23016 KB Output is correct
6 Correct 302 ms 23148 KB Output is correct
7 Correct 306 ms 23260 KB Output is correct
8 Correct 270 ms 22980 KB Output is correct
9 Correct 298 ms 22244 KB Output is correct
10 Correct 225 ms 22272 KB Output is correct
11 Correct 107 ms 15740 KB Output is correct
12 Correct 327 ms 22372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 22288 KB Output is correct
2 Correct 304 ms 22196 KB Output is correct
3 Correct 293 ms 22132 KB Output is correct
4 Correct 310 ms 22256 KB Output is correct
5 Correct 287 ms 22976 KB Output is correct
6 Correct 295 ms 23432 KB Output is correct
7 Correct 302 ms 24216 KB Output is correct
8 Correct 280 ms 22288 KB Output is correct
9 Correct 293 ms 22816 KB Output is correct
10 Correct 319 ms 22088 KB Output is correct
11 Correct 132 ms 15848 KB Output is correct
12 Correct 286 ms 23404 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4348 KB Output is correct
2 Correct 3 ms 2644 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 14 ms 6132 KB Output is correct
5 Correct 8 ms 4340 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 7 ms 4416 KB Output is correct
11 Correct 2 ms 2680 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 3 ms 2684 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 23316 KB Output is correct
2 Correct 282 ms 22236 KB Output is correct
3 Correct 300 ms 24544 KB Output is correct
4 Correct 263 ms 23048 KB Output is correct
5 Correct 273 ms 23016 KB Output is correct
6 Correct 302 ms 23148 KB Output is correct
7 Correct 306 ms 23260 KB Output is correct
8 Correct 270 ms 22980 KB Output is correct
9 Correct 298 ms 22244 KB Output is correct
10 Correct 225 ms 22272 KB Output is correct
11 Correct 107 ms 15740 KB Output is correct
12 Correct 327 ms 22372 KB Output is correct
13 Correct 294 ms 22288 KB Output is correct
14 Correct 304 ms 22196 KB Output is correct
15 Correct 293 ms 22132 KB Output is correct
16 Correct 310 ms 22256 KB Output is correct
17 Correct 287 ms 22976 KB Output is correct
18 Correct 295 ms 23432 KB Output is correct
19 Correct 302 ms 24216 KB Output is correct
20 Correct 280 ms 22288 KB Output is correct
21 Correct 293 ms 22816 KB Output is correct
22 Correct 319 ms 22088 KB Output is correct
23 Correct 132 ms 15848 KB Output is correct
24 Correct 286 ms 23404 KB Output is correct
25 Correct 9 ms 4348 KB Output is correct
26 Correct 3 ms 2644 KB Output is correct
27 Correct 2 ms 2688 KB Output is correct
28 Correct 14 ms 6132 KB Output is correct
29 Correct 8 ms 4340 KB Output is correct
30 Correct 3 ms 2772 KB Output is correct
31 Correct 3 ms 2772 KB Output is correct
32 Correct 3 ms 2900 KB Output is correct
33 Correct 2 ms 2772 KB Output is correct
34 Correct 7 ms 4416 KB Output is correct
35 Correct 2 ms 2680 KB Output is correct
36 Correct 2 ms 2668 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Correct 2 ms 2644 KB Output is correct
39 Correct 3 ms 2684 KB Output is correct
40 Correct 293 ms 22984 KB Output is correct
41 Correct 273 ms 22196 KB Output is correct
42 Correct 312 ms 22240 KB Output is correct
43 Correct 143 ms 16884 KB Output is correct
44 Correct 109 ms 16828 KB Output is correct
45 Correct 245 ms 24180 KB Output is correct
46 Correct 254 ms 24004 KB Output is correct
47 Correct 270 ms 23128 KB Output is correct
48 Correct 135 ms 16292 KB Output is correct
49 Correct 238 ms 22676 KB Output is correct
50 Correct 291 ms 24296 KB Output is correct
51 Correct 249 ms 24112 KB Output is correct