oj.uz

Submission #854843

# Submission time Handle Problem Language Result Execution time Memory
854843 2023-09-29T05:07:57 Z wibulord Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 362 ms 21004 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define db long double
#define fi first
#define se second
#define pb emplace_back
 
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pdd pair<db, db>
#define iii pair<int, pair<int, int> >
 
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(a) (ll)((a).size())
 
#define bit(x) bitset<10>((x))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (1 &((x) >> (i)))
#define clz(x) __builtin_clz((x))
#define ctz(x) __builtin_ctz((x))
#define popc(x) __builtin_popcount((x))
#define clzll(x) __builtin_clzll((x))
#define ctzll(x) __builtin_ctzll((x))
#define popcll(x) __builtin_popcountll((x))
 
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
#define rep(i, a) for (auto i : a)
 
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(long double x) {cerr << x;}
void print(double x) {cerr << x;}
void print(unsigned long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(bool x) {cerr << (x ? "True" : "False");}
void print(string x) {cerr << x;}
 
template <typename T,typename H>
void print(pair<T,H> a) {cerr << "("; print(a.fi); cerr << ','; print(a.se); cerr << ')';}
template <typename T>
void print(T vec) {int cnt=0; cerr << "{"; rep(x,vec) cerr << (cnt++?",":""), print(x); cerr << '}';}
 
void show() {}
template <typename Head, typename ...Tail>
void show(Head H, Tail ...T){
    print(H);
    if (sizeof...(T)) cerr << ", ";
    show(T...);
}
#define debug(X...) cerr << "LINE "  << __LINE__ << " - " <<  "[" << #X << "] = [", show(X), cerr << "]\n"
 
template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}
 
inline int gcd(int x,int y){while(y){int tmp=y;y=x%y;x=tmp;} return (x);}
inline int lcm(int x,int y){return (int)(x*y)/gcd(x,y);}
 
void read(){}
template <typename Head, typename ...Tail>
void read(Head &H, Tail &...T)
{
    int sign = 0;
    char c;
    for (c = getchar(); !isdigit(c); c = getchar())
        if (c == '-') sign = 1;
    H = c - '0';
    for (c = getchar(); isdigit(c); c = getchar())
        H = H * 10 + c - '0';
    if (sign) H = -H;
    read(T...);
}
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}
 
const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 1e5 + 1, M = 1e2 + 5;
 
/*
     /\_/\
    (= ._.)
    / >?  \>$
*/
int n, m, s, t, u, v;
ll du[N], dv[N], ds[N], dp[2][N], ans;
bool Free[N];
vii adj[N];
 
void dijkstra1(int src, ll d[]){
   ms(Free, 0);
   priority_queue<pli, vector<pli>, greater<pli>> q; q.push({0, src});
   while(sz(q)){
      int u = q.top().se;
      ll c = q.top().fi;
      q.pop();
      if(!Free[u]){
         Free[u] = 1;
         d[u] = c;
         for(auto [v, w] : adj[u]) q.push({w + c, v});
      }
   }
}
 
void dijkstra2(int src, int en){
  	ms(Free, 0); ms(dp, 0x3f);
   priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> q;
   q.push({0, {src, 0}});
 
   while(sz(q)){
      int u = q.top().se.fi;
      int p = q.top().se.se;
      ll c = q.top().fi;
      q.pop();
 
      if(!Free[u]){
         Free[u] = 1;
         ds[u] = c;
         ckmin(dp[0][u], min(du[u], dp[0][p]));
         ckmin(dp[1][u], min(dv[u], dp[1][p]));
         for(auto [v, w] : adj[u]) q.push({c + w, {v, u}});
      }
      else if(ds[u] == c){
         if(min(du[u], dp[0][p]) + min(dv[u], dp[1][p]) <= dp[0][u] + dp[1][u]){
            ckmin(dp[0][u], min(du[u], dp[0][p]));
            ckmin(dp[1][u], min(dv[u], dp[1][p]));
         }
      }
   }
   ckmin(ans, dp[0][en] + dp[1][en]);
}
 
void sol(){
   cin >> n >> m >> s >> t >> u >> v;
   F0R(i, m){
      int x, y, z; cin >> x >> y >> z;
      adj[x].pb(y, z); adj[y].pb(x, z);
   }
   dijkstra1(u, du); dijkstra1(v, dv);
 
   ans = du[v];
   dijkstra2(s, t); dijkstra2(t, s);
   cout << ans << endl;
}
 
signed main(){
    #define TASK "nhap"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
    }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra1(int, long long int*)':
commuter_pass.cpp:127:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |          for(auto [v, w] : adj[u]) q.push({w + c, v});
      |                   ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:148:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |          for(auto [v, w] : adj[u]) q.push({c + w, {v, u}});
      |                   ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 20776 KB Output is correct
2 Correct 317 ms 20520 KB Output is correct
3 Correct 311 ms 20836 KB Output is correct
4 Correct 340 ms 20360 KB Output is correct
5 Correct 304 ms 17028 KB Output is correct
6 Correct 341 ms 21004 KB Output is correct
7 Correct 328 ms 19916 KB Output is correct
8 Correct 311 ms 20732 KB Output is correct
9 Correct 335 ms 19672 KB Output is correct
10 Correct 335 ms 19700 KB Output is correct
11 Correct 61 ms 9784 KB Output is correct
12 Correct 362 ms 20676 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 19820 KB Output is correct
2 Correct 285 ms 18884 KB Output is correct
3 Correct 279 ms 20116 KB Output is correct
4 Correct 279 ms 16972 KB Output is correct
5 Correct 305 ms 16864 KB Output is correct
6 Correct 294 ms 19968 KB Output is correct
7 Correct 302 ms 20212 KB Output is correct
8 Correct 310 ms 17100 KB Output is correct
9 Correct 300 ms 20340 KB Output is correct
10 Correct 286 ms 20612 KB Output is correct
11 Correct 55 ms 9820 KB Output is correct
12 Correct 301 ms 20084 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8424 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Incorrect 2 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 20776 KB Output is correct
2 Correct 317 ms 20520 KB Output is correct
3 Correct 311 ms 20836 KB Output is correct
4 Correct 340 ms 20360 KB Output is correct
5 Correct 304 ms 17028 KB Output is correct
6 Correct 341 ms 21004 KB Output is correct
7 Correct 328 ms 19916 KB Output is correct
8 Correct 311 ms 20732 KB Output is correct
9 Correct 335 ms 19672 KB Output is correct
10 Correct 335 ms 19700 KB Output is correct
11 Correct 61 ms 9784 KB Output is correct
12 Correct 362 ms 20676 KB Output is correct
13 Correct 321 ms 19820 KB Output is correct
14 Correct 285 ms 18884 KB Output is correct
15 Correct 279 ms 20116 KB Output is correct
16 Correct 279 ms 16972 KB Output is correct
17 Correct 305 ms 16864 KB Output is correct
18 Correct 294 ms 19968 KB Output is correct
19 Correct 302 ms 20212 KB Output is correct
20 Correct 310 ms 17100 KB Output is correct
21 Correct 300 ms 20340 KB Output is correct
22 Correct 286 ms 20612 KB Output is correct
23 Correct 55 ms 9820 KB Output is correct
24 Correct 301 ms 20084 KB Output is correct
25 Correct 27 ms 8424 KB Output is correct
26 Correct 2 ms 6748 KB Output is correct
27 Incorrect 2 ms 6748 KB Output isn't correct
28 Halted 0 ms 0 KB -