oj.uz

답안 #854838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854838 2023-09-29T04:59:27 Z wibulord Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 260 ms 21240 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) int((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[]){
   memset(Free, 0, (n+1)*sizeof(bool));
   memset(d, 0x3f, (n+1)*sizeof(ll)); d[src] = 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]) continue;
      Free[u] = 1;
      for(auto [v, w] : adj[u]) if(!Free[v] && d[v] > d[u] + w){
         d[v] = d[u] + w;
         q.push({d[v], v});
      }
   }
}

void dijkstra2(int src, int en){
   memset(Free, 0, (n+1)*sizeof(bool));
   memset(dp[0], 0x3f, (n+1)*sizeof(ll));
   memset(dp[1], 0x3f, (n+1)*sizeof(ll));
   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:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |       for(auto [v, w] : adj[u]) if(!Free[v] && d[v] > d[u] + w){
      |                ^
commuter_pass.cpp:123:10: warning: unused variable 'c' [-Wunused-variable]
  123 |       ll c = q.top().fi;
      |          ^
commuter_pass.cpp: In function 'void dijkstra2(int, int)':
commuter_pass.cpp:152:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |          for(auto [v, w] : adj[u]) q.push({c + w, {v, u}});
      |                   ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:180:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 19952 KB Output is correct
2 Correct 225 ms 20148 KB Output is correct
3 Correct 231 ms 20848 KB Output is correct
4 Correct 246 ms 21240 KB Output is correct
5 Correct 235 ms 16976 KB Output is correct
6 Correct 250 ms 20684 KB Output is correct
7 Correct 238 ms 21208 KB Output is correct
8 Correct 240 ms 20804 KB Output is correct
9 Correct 259 ms 19720 KB Output is correct
10 Correct 242 ms 19784 KB Output is correct
11 Correct 56 ms 9812 KB Output is correct
12 Correct 260 ms 19696 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 19496 KB Output is correct
2 Correct 224 ms 17104 KB Output is correct
3 Correct 238 ms 19448 KB Output is correct
4 Correct 221 ms 17060 KB Output is correct
5 Correct 231 ms 16928 KB Output is correct
6 Correct 226 ms 20080 KB Output is correct
7 Correct 239 ms 16964 KB Output is correct
8 Correct 225 ms 17000 KB Output is correct
9 Correct 240 ms 16924 KB Output is correct
10 Correct 251 ms 20356 KB Output is correct
11 Correct 59 ms 9940 KB Output is correct
12 Correct 229 ms 20476 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8212 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 19952 KB Output is correct
2 Correct 225 ms 20148 KB Output is correct
3 Correct 231 ms 20848 KB Output is correct
4 Correct 246 ms 21240 KB Output is correct
5 Correct 235 ms 16976 KB Output is correct
6 Correct 250 ms 20684 KB Output is correct
7 Correct 238 ms 21208 KB Output is correct
8 Correct 240 ms 20804 KB Output is correct
9 Correct 259 ms 19720 KB Output is correct
10 Correct 242 ms 19784 KB Output is correct
11 Correct 56 ms 9812 KB Output is correct
12 Correct 260 ms 19696 KB Output is correct
13 Correct 248 ms 19496 KB Output is correct
14 Correct 224 ms 17104 KB Output is correct
15 Correct 238 ms 19448 KB Output is correct
16 Correct 221 ms 17060 KB Output is correct
17 Correct 231 ms 16928 KB Output is correct
18 Correct 226 ms 20080 KB Output is correct
19 Correct 239 ms 16964 KB Output is correct
20 Correct 225 ms 17000 KB Output is correct
21 Correct 240 ms 16924 KB Output is correct
22 Correct 251 ms 20356 KB Output is correct
23 Correct 59 ms 9940 KB Output is correct
24 Correct 229 ms 20476 KB Output is correct
25 Correct 17 ms 8212 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Incorrect 1 ms 6748 KB Output isn't correct
28 Halted 0 ms 0 KB -