oj.uz

Submission #649792

# Submission time Handle Problem Language Result Execution time Memory
649792 2022-10-11T10:57:06 Z birthdaycake Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 685 ms 30860 KB 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
 
 
 
// - - - - - -
 
 
// #include<bits/stdc++.h>
using namespace std;
#define int long long
 
vector<pair<int,int>>adj[200001];
int ans = 1e18;
int dij[5][100001];
int best[100001];
vector<int>a1[100001];
vector<int>a2[100001];
signed main(){
    int n,m; cin >> n >> m;
    int s,t; cin >> s >> t;
    int u,v; cin >> u >> v;
    for(int i = 0; i < m; i++){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    set<pair<int,int>>d;
    for(int i = 1; i <= n; i++){
        dij[0][i] = dij[1][i] = dij[2][i] = dij[3][i] = 1e18;
    }
    dij[0][s] = 0;
    d.insert({dij[0][s], s});
    while(d.size()){
        auto s = *d.begin();
        d.erase(s);
        if(dij[0][s.second] < s.first) continue;
        dij[0][s.second] = s.first;
        for(auto x:adj[s.second]){
            if(dij[0][s.second] + x.second < dij[0][x.first]){
                best[x.first] = s.second;
                dij[0][x.first] = dij[0][s.second] + x.second;
                d.insert({dij[0][x.first], x.first});
            }
        }
    }
    dij[1][t] = 0;
    d.insert({dij[1][t], t});
    while(d.size()){
        auto s = *d.begin();
        d.erase(s);
        if(dij[1][s.second] < s.first) continue;
        dij[1][s.second] = s.first;
        for(auto x:adj[s.second]){
            if(dij[1][s.second] + x.second < dij[1][x.first]){
                dij[1][x.first] = dij[1][s.second] + x.second;
                d.insert({dij[1][x.first], x.first});
            }
        }
    }
    dij[2][v] = 0;
    d.insert({dij[2][v], v});
    while(d.size()){
        auto s = *d.begin();
        d.erase(s);
        if(dij[2][s.second] < s.first) continue;
        dij[2][s.second] = s.first;
        for(auto x:adj[s.second]){
            if(dij[2][s.second] + x.second < dij[2][x.first]){
                dij[2][x.first] = dij[2][s.second] + x.second;
                d.insert({dij[2][x.first], x.first});
            }
        }
    }
    dij[3][u] = 0;
    d.insert({dij[3][u], u});
    while(d.size()){
        auto s = *d.begin();
        d.erase(s);
        if(dij[3][s.second] < s.first) continue;
        dij[3][s.second] = s.first;
        for(auto x:adj[s.second]){
            if(dij[3][s.second] + x.second < dij[3][x.first]){
                dij[3][x.first] = dij[3][s.second] + x.second;
                d.insert({dij[3][x.first], x.first});
            }
        }
    }
    ans = dij[3][v];
    vector<pair<int,int>>a1,a2;
    for(int i = 1; i <= n; i++){
        if(dij[0][i] + dij[1][i] != dij[0][t]) continue;
        a1.push_back({dij[3][i],i});
        a2.push_back({dij[2][i],i});
    }
    sort(a1.begin(), a1.end());
    sort(a2.begin(), a2.end());
    ans = min(ans,a1[0].first + a2[1].first);
    ans = min(ans,a1[1].first + a2[0].first);
    ans = min(ans,a1[0].first + a2[0].first);
    
    
    cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 27968 KB Output is correct
2 Correct 493 ms 27392 KB Output is correct
3 Correct 542 ms 30860 KB Output is correct
4 Correct 616 ms 27952 KB Output is correct
5 Correct 489 ms 27624 KB Output is correct
6 Correct 622 ms 28412 KB Output is correct
7 Correct 552 ms 29376 KB Output is correct
8 Correct 589 ms 27552 KB Output is correct
9 Correct 565 ms 26768 KB Output is correct
10 Correct 518 ms 26192 KB Output is correct
11 Correct 216 ms 20572 KB Output is correct
12 Correct 625 ms 26872 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 27704 KB Output is correct
2 Correct 650 ms 27136 KB Output is correct
3 Correct 591 ms 27156 KB Output is correct
4 Correct 613 ms 27152 KB Output is correct
5 Correct 642 ms 27672 KB Output is correct
6 Correct 580 ms 29336 KB Output is correct
7 Correct 612 ms 30292 KB Output is correct
8 Correct 622 ms 27092 KB Output is correct
9 Correct 578 ms 28272 KB Output is correct
10 Correct 609 ms 27116 KB Output is correct
11 Correct 255 ms 21000 KB Output is correct
12 Correct 543 ms 28680 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11072 KB Output is correct
2 Correct 6 ms 9684 KB Output is correct
3 Incorrect 8 ms 9680 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 27968 KB Output is correct
2 Correct 493 ms 27392 KB Output is correct
3 Correct 542 ms 30860 KB Output is correct
4 Correct 616 ms 27952 KB Output is correct
5 Correct 489 ms 27624 KB Output is correct
6 Correct 622 ms 28412 KB Output is correct
7 Correct 552 ms 29376 KB Output is correct
8 Correct 589 ms 27552 KB Output is correct
9 Correct 565 ms 26768 KB Output is correct
10 Correct 518 ms 26192 KB Output is correct
11 Correct 216 ms 20572 KB Output is correct
12 Correct 625 ms 26872 KB Output is correct
13 Correct 685 ms 27704 KB Output is correct
14 Correct 650 ms 27136 KB Output is correct
15 Correct 591 ms 27156 KB Output is correct
16 Correct 613 ms 27152 KB Output is correct
17 Correct 642 ms 27672 KB Output is correct
18 Correct 580 ms 29336 KB Output is correct
19 Correct 612 ms 30292 KB Output is correct
20 Correct 622 ms 27092 KB Output is correct
21 Correct 578 ms 28272 KB Output is correct
22 Correct 609 ms 27116 KB Output is correct
23 Correct 255 ms 21000 KB Output is correct
24 Correct 543 ms 28680 KB Output is correct
25 Correct 26 ms 11072 KB Output is correct
26 Correct 6 ms 9684 KB Output is correct
27 Incorrect 8 ms 9680 KB Output isn't correct
28 Halted 0 ms 0 KB -