oj.uz

Submission #944863

# Submission time Handle Problem Language Result Execution time Memory
944863 2024-03-13T06:51:39 Z Amaarsaa Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 373 ms 26300 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define vi vector<int>
#define vl vector<long long>
#define vii vector<pair<int,int>>
#define vll vector<pair<long long,long long>>
#define pb push_back
#define ll long long
#define ld long double
#define nl '\n'
#define boost ios::sync_with_stdio(false)
#define mp make_pair
#define se second
#define fi first
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i,x,y) for(int i = x;i<=y;i++)
#define forn(i,y,x) for(int i = y; i >= x; i--)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define clr(v,k) memset(v,k,sizeof(v))
#define rall(v) v.rbegin() , v.rend()
#define pii pair<int,int>
#define pll pair<ll , ll>

const ll MOD = 1e9 + 7;
const int INF = 1e18 + 1;
const int inf = 1e9 + 1;

ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (gcd)
ll lcm(ll a , ll b) {return a * (b / gcd(a , b));} // least common multiple (lcm)

// HERE IS THE SOLUTION
const int N = 100000;
vii adj[N];
vi dp(N , INF) , dp0(N , INF);
int n , m , s , t , u , v;
vi spS , spT , spV , spU;
int dfs(int x)
{
    int &ans = dp[x];
    if(ans != INF)
        return ans;
    ans = spV[x];
    for(auto [y,c] : adj[x])
    {
        if(spS[x] + spT[y] + c== spS[t])
            ans = min(ans , dfs(y));
    }
    return ans;
}
int dfs0(int x)
{
    int &ans = dp0[x];
    if(ans != INF)
        return ans;
    ans = spV[x];
    for(auto [y,c] : adj[x])
    {
        if(spS[y] + spT[x] + c== spS[t])
            ans = min(ans , dfs0(y));
    }
    return ans;
}
vi  dijkstra(int start)
{
    vi dist(n , INF);
    priority_queue<pii> pq;
    pq.push({0 , start});
    dist[start] = 0;
    vector<bool> vis(n , 0);
    while(!pq.empty())
    {
        int cur = pq.top().se;
        pq.pop();
        if(vis[cur])
            continue;
        vis[cur] = 1;
        for(auto [x , c] : adj[cur])
        {
            if(dist[x] > dist[cur] + c){
                dist[x] = dist[cur] + c;
                pq.push({-dist[x] , x});
            }
        }
    }
    return dist;
}
bool cmp(int &a , int &b)
{
    return spS[a] < spS[b];
}
signed main()
{

    cin>>n>>m>>s>>t>>u>>v;
    u-- , v-- , t-- , s--;
    fore(i , m)
    {
        int a , b,c;
        cin>>a>>b>>c;
        a-- , b--;
        adj[a].pb({b , c});
        adj[b].pb({a , c});
    }
    spS = dijkstra(s) , spT = dijkstra(t) , spV = dijkstra(v) , spU = dijkstra(u);
    int ans = INF;
    vi vv;
    fore(i , n)
    {
        vv.pb(i);
    }
//    sort(all(vv) , cmp);
    for(auto x : vv)
    {
        if(spS[x]+spT[x] == spS[t])
            ans = min(ans , min(dfs0(x) ,dfs(x)) + spU[x]);
    }
    cout<<min(ans , spU[v])<<nl;
}

Compilation message

commuter_pass.cpp: In function 'long long int dfs(long long int)':
commuter_pass.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [y,c] : adj[x])
      |              ^
commuter_pass.cpp: In function 'long long int dfs0(long long int)':
commuter_pass.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto [y,c] : adj[x])
      |              ^
commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(long long int)':
commuter_pass.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         for(auto [x , c] : adj[cur])
      |                  ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 20872 KB Output is correct
2 Correct 274 ms 19752 KB Output is correct
3 Correct 313 ms 22000 KB Output is correct
4 Correct 267 ms 23960 KB Output is correct
5 Correct 276 ms 23156 KB Output is correct
6 Correct 289 ms 24864 KB Output is correct
7 Correct 286 ms 23200 KB Output is correct
8 Correct 303 ms 23400 KB Output is correct
9 Correct 283 ms 24032 KB Output is correct
10 Correct 263 ms 24112 KB Output is correct
11 Correct 106 ms 17864 KB Output is correct
12 Correct 329 ms 23948 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 21200 KB Output is correct
2 Correct 276 ms 21108 KB Output is correct
3 Correct 291 ms 21072 KB Output is correct
4 Correct 337 ms 25292 KB Output is correct
5 Correct 294 ms 24544 KB Output is correct
6 Correct 317 ms 26300 KB Output is correct
7 Correct 299 ms 26072 KB Output is correct
8 Correct 335 ms 24092 KB Output is correct
9 Correct 288 ms 24528 KB Output is correct
10 Correct 373 ms 24780 KB Output is correct
11 Correct 121 ms 19048 KB Output is correct
12 Correct 300 ms 25896 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5720 KB Output is correct
2 Correct 2 ms 4184 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 28 ms 7812 KB Output is correct
5 Correct 15 ms 6232 KB Output is correct
6 Correct 3 ms 4444 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Correct 4 ms 4696 KB Output is correct
9 Correct 3 ms 4696 KB Output is correct
10 Correct 18 ms 6236 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 2 ms 4416 KB Output is correct
13 Correct 2 ms 4184 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 20872 KB Output is correct
2 Correct 274 ms 19752 KB Output is correct
3 Correct 313 ms 22000 KB Output is correct
4 Correct 267 ms 23960 KB Output is correct
5 Correct 276 ms 23156 KB Output is correct
6 Correct 289 ms 24864 KB Output is correct
7 Correct 286 ms 23200 KB Output is correct
8 Correct 303 ms 23400 KB Output is correct
9 Correct 283 ms 24032 KB Output is correct
10 Correct 263 ms 24112 KB Output is correct
11 Correct 106 ms 17864 KB Output is correct
12 Correct 329 ms 23948 KB Output is correct
13 Correct 275 ms 21200 KB Output is correct
14 Correct 276 ms 21108 KB Output is correct
15 Correct 291 ms 21072 KB Output is correct
16 Correct 337 ms 25292 KB Output is correct
17 Correct 294 ms 24544 KB Output is correct
18 Correct 317 ms 26300 KB Output is correct
19 Correct 299 ms 26072 KB Output is correct
20 Correct 335 ms 24092 KB Output is correct
21 Correct 288 ms 24528 KB Output is correct
22 Correct 373 ms 24780 KB Output is correct
23 Correct 121 ms 19048 KB Output is correct
24 Correct 300 ms 25896 KB Output is correct
25 Correct 15 ms 5720 KB Output is correct
26 Correct 2 ms 4184 KB Output is correct
27 Correct 2 ms 4440 KB Output is correct
28 Correct 28 ms 7812 KB Output is correct
29 Correct 15 ms 6232 KB Output is correct
30 Correct 3 ms 4444 KB Output is correct
31 Correct 3 ms 4444 KB Output is correct
32 Correct 4 ms 4696 KB Output is correct
33 Correct 3 ms 4696 KB Output is correct
34 Correct 18 ms 6236 KB Output is correct
35 Correct 2 ms 4188 KB Output is correct
36 Correct 2 ms 4416 KB Output is correct
37 Correct 2 ms 4184 KB Output is correct
38 Correct 2 ms 4444 KB Output is correct
39 Correct 2 ms 4444 KB Output is correct
40 Correct 286 ms 25044 KB Output is correct
41 Correct 309 ms 24180 KB Output is correct
42 Correct 284 ms 24016 KB Output is correct
43 Correct 123 ms 18252 KB Output is correct
44 Correct 124 ms 18628 KB Output is correct
45 Correct 282 ms 22928 KB Output is correct
46 Correct 263 ms 22796 KB Output is correct
47 Correct 289 ms 23724 KB Output is correct
48 Correct 112 ms 16076 KB Output is correct
49 Correct 265 ms 24312 KB Output is correct
50 Correct 270 ms 22992 KB Output is correct
51 Correct 261 ms 23324 KB Output is correct