oj.uz

Submission #500093

# Submission time Handle Problem Language Result Execution time Memory
500093 2021-12-30T10:10:22 Z aSSSd Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 334 ms 23128 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define iii pair<ii,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair<int,int>
#define mt make_tuple
#define getbit(x,i) ((x>>(i))&1)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))
#define endl '\n'
#define all(v) v.begin(), v.end()
#define gg exit(0);
#define int long long
const int N = 1e5 + 1000;
int n,m;
vector<ii> ke[N];
int s, t, u, v;
vector<int>  ditcha(int st)
{
    vector<int> d(n+1,1e16);
    priority_queue<ii, vector<ii>, greater<ii> > q;
    q.push({0, st});
    d[st] =0;
    while(!q.empty())
    {
        ii u = q.top();
        q.pop();
        if(u.fi != d[u.se]) continue;
        for(auto v : ke[u.se])
        {
            int cost = v.se;
            if(d[v.fi] > d[u.se] + v.se)
            {
                d[v.fi] = d[u.se] + v.se;
                q.push({d[v.fi], v.fi});
            }
        }
    }
    return  d;
}
int f[N], dp[N];
main()
{
   // freopen("task.inp" , "r" , stdin);
    fasty;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    forinc(i,1,m)
    {
        int u, v, c;
        cin >> u >> v >>c;
        ke[u].pb({v,c});
        ke[v].pb({u,c});
    }
    vector<int> ds = ditcha(s);
    vector<int> dt = ditcha(t);
    vector<int> du = ditcha(u);
    vector<int> dv = ditcha(v);
    //cout << du[v] << "\n";
  //  cout << du[s] << "\n";
    int res = 1e18;
    for(int _ = 0 ; _ < 2 ; _++)
    {
        priority_queue<ii, vector<ii>, greater<ii> > q;
        forinc(i,0,n+1) dp[i] = 1e16;
        forinc(i,0,n+1) f[i] = 1e16;
        f[s]=0;
        dp[s] = du[s];
        //cout << dp[s] << " ";
        q.push({0,s});
        while(!q.empty())
        {
            ii u = q.top();
            q.pop();
            if(f[u.se] != u.fi) continue;
            //u - i
            //cout << dp[u.se] + dv[u.se] << "\n";
            //cout << u.se << " " << dp[u.se] << " " << dv[u.se] << "\n";
            //gg;
            res = min(res, dp[u.se] + dv[u.se]);
            //cout << res << " ";
           // s ----- u ------ v ----- t
            for(auto v : ke[u.se])
            {
                if(ds[v.fi] + dt[v.fi] == ds[t] )
                {
                    dp[v.fi] = min({dp[v.fi] , dp[u.se] , du[u.se]} );
                    if(f[v.fi] > v.se + f[u.se])
                    {
                        f[v.fi] = v.se + f[u.se];
                        q.push({f[v.fi], v.fi});
                    }
                }
            }
        }
        //cout << "co swap ko >> ";
        swap(du,dv);
    }
   // cout << res << "\n";
    res = min(res , du[v]);
    cout << res;

}

Compilation message

commuter_pass.cpp: In function 'std::vector<long long int> ditcha(long long int)':
commuter_pass.cpp:42:17: warning: unused variable 'cost' [-Wunused-variable]
   42 |             int cost = v.se;
      |                 ^~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main()
      | ^~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 19488 KB Output is correct
2 Correct 271 ms 18296 KB Output is correct
3 Correct 304 ms 19640 KB Output is correct
4 Correct 246 ms 19360 KB Output is correct
5 Correct 283 ms 18176 KB Output is correct
6 Correct 274 ms 19656 KB Output is correct
7 Correct 312 ms 18196 KB Output is correct
8 Correct 289 ms 18144 KB Output is correct
9 Correct 275 ms 18232 KB Output is correct
10 Correct 239 ms 18036 KB Output is correct
11 Correct 110 ms 12652 KB Output is correct
12 Correct 272 ms 18208 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 18248 KB Output is correct
2 Correct 303 ms 18260 KB Output is correct
3 Correct 293 ms 18176 KB Output is correct
4 Correct 284 ms 18180 KB Output is correct
5 Correct 314 ms 18300 KB Output is correct
6 Correct 321 ms 18580 KB Output is correct
7 Correct 334 ms 18924 KB Output is correct
8 Correct 291 ms 18224 KB Output is correct
9 Correct 332 ms 18220 KB Output is correct
10 Correct 302 ms 21516 KB Output is correct
11 Correct 126 ms 14668 KB Output is correct
12 Correct 323 ms 22472 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4120 KB Output is correct
2 Correct 2 ms 2704 KB Output is correct
3 Correct 2 ms 2704 KB Output is correct
4 Correct 13 ms 5560 KB Output is correct
5 Correct 7 ms 4120 KB Output is correct
6 Correct 2 ms 2840 KB Output is correct
7 Correct 3 ms 2836 KB Output is correct
8 Correct 3 ms 2992 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 8 ms 4328 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2764 KB Output is correct
14 Correct 2 ms 2708 KB Output is correct
15 Correct 2 ms 2700 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 19488 KB Output is correct
2 Correct 271 ms 18296 KB Output is correct
3 Correct 304 ms 19640 KB Output is correct
4 Correct 246 ms 19360 KB Output is correct
5 Correct 283 ms 18176 KB Output is correct
6 Correct 274 ms 19656 KB Output is correct
7 Correct 312 ms 18196 KB Output is correct
8 Correct 289 ms 18144 KB Output is correct
9 Correct 275 ms 18232 KB Output is correct
10 Correct 239 ms 18036 KB Output is correct
11 Correct 110 ms 12652 KB Output is correct
12 Correct 272 ms 18208 KB Output is correct
13 Correct 289 ms 18248 KB Output is correct
14 Correct 303 ms 18260 KB Output is correct
15 Correct 293 ms 18176 KB Output is correct
16 Correct 284 ms 18180 KB Output is correct
17 Correct 314 ms 18300 KB Output is correct
18 Correct 321 ms 18580 KB Output is correct
19 Correct 334 ms 18924 KB Output is correct
20 Correct 291 ms 18224 KB Output is correct
21 Correct 332 ms 18220 KB Output is correct
22 Correct 302 ms 21516 KB Output is correct
23 Correct 126 ms 14668 KB Output is correct
24 Correct 323 ms 22472 KB Output is correct
25 Correct 8 ms 4120 KB Output is correct
26 Correct 2 ms 2704 KB Output is correct
27 Correct 2 ms 2704 KB Output is correct
28 Correct 13 ms 5560 KB Output is correct
29 Correct 7 ms 4120 KB Output is correct
30 Correct 2 ms 2840 KB Output is correct
31 Correct 3 ms 2836 KB Output is correct
32 Correct 3 ms 2992 KB Output is correct
33 Correct 2 ms 2764 KB Output is correct
34 Correct 8 ms 4328 KB Output is correct
35 Correct 2 ms 2636 KB Output is correct
36 Correct 2 ms 2636 KB Output is correct
37 Correct 2 ms 2764 KB Output is correct
38 Correct 2 ms 2708 KB Output is correct
39 Correct 2 ms 2700 KB Output is correct
40 Correct 246 ms 23128 KB Output is correct
41 Correct 265 ms 22264 KB Output is correct
42 Correct 282 ms 22372 KB Output is correct
43 Correct 130 ms 14736 KB Output is correct
44 Correct 166 ms 14660 KB Output is correct
45 Correct 310 ms 22784 KB Output is correct
46 Correct 332 ms 22440 KB Output is correct
47 Correct 254 ms 23028 KB Output is correct
48 Correct 139 ms 14104 KB Output is correct
49 Correct 198 ms 22704 KB Output is correct
50 Correct 298 ms 22072 KB Output is correct
51 Correct 278 ms 22728 KB Output is correct