oj.uz

Submission #833039

# Submission time Handle Problem Language Result Execution time Memory
833039 2023-08-21T20:24:37 Z Saacoota Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 283 ms 26680 KB 
#include    <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b)  for(int i=(a);i<(b);++i)
#define fi  first
#define se  second
#define LL  unsigned long long
#define uint unsigned int
#define pb  push_back
#define eb  emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <long long , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "commuter"
using   namespace   std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5 + 5;
int n , m , tim , s , t;
long long d[maxn][4] , dp[maxn] , res , ans;
ii a[maxn];
bool vs[maxn] ;
vector < ii > g[maxn];
vector < int > adj[maxn];
///--------------------------
void dijkstra(int u,int ty) {
    priority_queue < ii , vector < ii > , greater < ii > > pt;
    d[u][ty] = 0;
    pt.push({d[u][ty] , u});
    while (!pt.empty()) {
        ii x = pt.top();
        pt.pop();
        long long dis = x.fi;
        int u = x.se;
        if (dis != d[u][ty]) continue;
        for (auto v : g[u]) {
            if (d[v.fi][ty] > dis + v.se) {
                d[v.fi][ty] = dis + v.se;
                pt.push({d[v.fi][ty] , v.fi});
            }
        }
    }
}
///--------------------------
void readf() {
    int u , v;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1 ; i <= m ; ++i) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].eb(v , w);
        g[v].eb(u , w);
    }
    memset(d,inf,sizeof(d));
    memset(dp,inf,sizeof(dp));
    dijkstra(s,0);
    dijkstra(u,1);
    dijkstra(v,2);
    dijkstra(t,3);
    ans = res = d[v][1];
}
///--------------------------
bool in(int u) {
    return (d[u][0] + d[u][3] == d[t][0]);
}
///--------------------------
void solve() {
    for (int i = 1 ; i <= n ; ++i) a[i] = ii(d[i][0] , i);
    sort(a + 1 , a + n + 1);

    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) dp[u] = d[u][2];
    for (int i = n ; i > 0 ; --i) {
        int u = a[i].se;
        if (!in(u)) continue;
        for (auto v : g[u])
        if (in(v.fi) && d[v.fi][0] == d[u][0] + v.se) {
            dp[u] = min(dp[u] , dp[v.fi]);
        }
    }
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) res = min(res , dp[u] + d[u][1]);

    memset(dp,inf,sizeof(dp));
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) dp[u] = d[u][1];
    for (int i = n ; i > 0 ; --i) {
        int u = a[i].se;
        if (!in(u)) continue;
        for (auto v : g[u])
        if (in(v.fi) && d[v.fi][0] == d[u][0] + v.se) {
            dp[u] = min(dp[u] , dp[v.fi]);
        }
    }
    for (int u = 1 ; u <= n ; ++u)
    if (in(u)) res = min(res , dp[u] + d[u][2]);
    cout << res << '\n';
}
///--------------------------
void solve1() {
    for (int u = 1 ; u <= n ; ++u)
    for (int v = 1 ; v <= n ; ++v)
    if (in(u) && in(v)) ans = min(ans , d[u][1] + d[v][2]);
    cout << ans << '\n';
}
///--------------------------
int main() {
   #ifdef BDP0509
       freopen(TASK".inp", "r", stdin);
       freopen(TASK".out", "w", stdout);
   #endif // ONLINE_JUDGE
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   solve();
   //solve1();
}

Compilation message

commuter_pass.cpp: In function 'void readf()':
commuter_pass.cpp:55:14: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   55 |     memset(d,inf,sizeof(d));
      |              ^~~
commuter_pass.cpp:56:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   56 |     memset(dp,inf,sizeof(dp));
      |               ^~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:85:15: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
   85 |     memset(dp,inf,sizeof(dp));
      |               ^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 23696 KB Output is correct
2 Correct 237 ms 24748 KB Output is correct
3 Correct 253 ms 26044 KB Output is correct
4 Correct 233 ms 26680 KB Output is correct
5 Correct 230 ms 24440 KB Output is correct
6 Correct 260 ms 26368 KB Output is correct
7 Correct 247 ms 24644 KB Output is correct
8 Correct 262 ms 24788 KB Output is correct
9 Correct 245 ms 25508 KB Output is correct
10 Correct 202 ms 25508 KB Output is correct
11 Correct 84 ms 17728 KB Output is correct
12 Correct 275 ms 25372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 22568 KB Output is correct
2 Correct 259 ms 24700 KB Output is correct
3 Correct 279 ms 24696 KB Output is correct
4 Correct 263 ms 24844 KB Output is correct
5 Correct 280 ms 24852 KB Output is correct
6 Correct 239 ms 24956 KB Output is correct
7 Correct 238 ms 24688 KB Output is correct
8 Correct 278 ms 24700 KB Output is correct
9 Correct 283 ms 24688 KB Output is correct
10 Correct 269 ms 24684 KB Output is correct
11 Correct 98 ms 17888 KB Output is correct
12 Correct 248 ms 25012 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10708 KB Output is correct
2 Correct 4 ms 8916 KB Output is correct
3 Correct 4 ms 8880 KB Output is correct
4 Correct 13 ms 12372 KB Output is correct
5 Correct 9 ms 10580 KB Output is correct
6 Correct 4 ms 9044 KB Output is correct
7 Correct 5 ms 9088 KB Output is correct
8 Correct 7 ms 9172 KB Output is correct
9 Correct 4 ms 9044 KB Output is correct
10 Correct 8 ms 10580 KB Output is correct
11 Correct 4 ms 8916 KB Output is correct
12 Correct 5 ms 8916 KB Output is correct
13 Correct 4 ms 9000 KB Output is correct
14 Correct 4 ms 8916 KB Output is correct
15 Correct 6 ms 8916 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 23696 KB Output is correct
2 Correct 237 ms 24748 KB Output is correct
3 Correct 253 ms 26044 KB Output is correct
4 Correct 233 ms 26680 KB Output is correct
5 Correct 230 ms 24440 KB Output is correct
6 Correct 260 ms 26368 KB Output is correct
7 Correct 247 ms 24644 KB Output is correct
8 Correct 262 ms 24788 KB Output is correct
9 Correct 245 ms 25508 KB Output is correct
10 Correct 202 ms 25508 KB Output is correct
11 Correct 84 ms 17728 KB Output is correct
12 Correct 275 ms 25372 KB Output is correct
13 Correct 254 ms 22568 KB Output is correct
14 Correct 259 ms 24700 KB Output is correct
15 Correct 279 ms 24696 KB Output is correct
16 Correct 263 ms 24844 KB Output is correct
17 Correct 280 ms 24852 KB Output is correct
18 Correct 239 ms 24956 KB Output is correct
19 Correct 238 ms 24688 KB Output is correct
20 Correct 278 ms 24700 KB Output is correct
21 Correct 283 ms 24688 KB Output is correct
22 Correct 269 ms 24684 KB Output is correct
23 Correct 98 ms 17888 KB Output is correct
24 Correct 248 ms 25012 KB Output is correct
25 Correct 10 ms 10708 KB Output is correct
26 Correct 4 ms 8916 KB Output is correct
27 Correct 4 ms 8880 KB Output is correct
28 Correct 13 ms 12372 KB Output is correct
29 Correct 9 ms 10580 KB Output is correct
30 Correct 4 ms 9044 KB Output is correct
31 Correct 5 ms 9088 KB Output is correct
32 Correct 7 ms 9172 KB Output is correct
33 Correct 4 ms 9044 KB Output is correct
34 Correct 8 ms 10580 KB Output is correct
35 Correct 4 ms 8916 KB Output is correct
36 Correct 5 ms 8916 KB Output is correct
37 Correct 4 ms 9000 KB Output is correct
38 Correct 4 ms 8916 KB Output is correct
39 Correct 6 ms 8916 KB Output is correct
40 Correct 232 ms 26232 KB Output is correct
41 Correct 245 ms 25396 KB Output is correct
42 Correct 269 ms 25460 KB Output is correct
43 Correct 99 ms 17784 KB Output is correct
44 Correct 94 ms 17868 KB Output is correct
45 Correct 228 ms 24400 KB Output is correct
46 Correct 261 ms 24152 KB Output is correct
47 Correct 252 ms 26116 KB Output is correct
48 Correct 94 ms 17216 KB Output is correct
49 Correct 179 ms 25816 KB Output is correct
50 Correct 265 ms 24472 KB Output is correct
51 Correct 219 ms 24352 KB Output is correct