oj.uz

Submission #884031

# Submission time Handle Problem Language Result Execution time Memory
884031 2023-12-06T14:47:02 Z nasam Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 216 ms 17612 KB 
/*************************************
*       author: Pham Huy Khanh       *
*************************************/
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FOD(i,b,a) for (int i = (b), _a = (a); i >= _a; i--)
#define ALL(v) (v).begin(), (v).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define CNTBIT(x) __builtin_popcount(x)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define left ___left
#define right ___right
#define pii pair<int, int>
#define DEBUG(n, a) FOR (i, 1, n) cout << a[i] << ' '; cout << endl;
#define endl "\n"

using namespace std;

template<class X, class Y> bool maximize(X &x, Y y){ if (x < y){ x = y; return true; } return false; }
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y){ x = y; return true; } return false; }

#define  gogobruhbruh  ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

const int MOD = 1e9 + 7;

void add(ll &a, ll b){ if ((a += b) >= MOD) a -= MOD; }
void sub(ll &a, ll b){ if ((a -= b) < 0) a += MOD; }
int muti(int a, int b){ return 1LL * a * b % MOD; }
int Pow(int a, int b){ int res = 1; for (; b; b >>= 1, a = muti(a, a)) if (b & 1) res = muti(res, a); return res; }

const int MAX = 1e5 + 7;
const int INF = 1e9 + 7;

int numNode, numEdge, s, t, a, b;
vector<pii> edge[MAX];
ll dis[MAX][4];
priority_queue<pair<ll, int>> heap;

void pfs(int u, int i){
    dis[u][i] = 0;
    heap.push({0, u});
    while (heap.size()){
        auto [cur, u] = heap.top(); heap.pop();
        if (-cur > dis[u][i])
            continue;
        for (auto [v, cost] : edge[u]){
            if (i > 1 && dis[u][i - 2] + dis[v][(i - 2) ^ 1] + cost == dis[t][0])
                cost = 0;
            if (minimize(dis[v][i], dis[u][i] + cost))
                heap.push({-dis[v][i], v});
        }
    }
}

void solve(){
    memset(dis, 0x3f, sizeof(dis));
    pfs(s, 0); pfs(t, 1); pfs(a, 2); pfs(a, 3);
    cout << min(dis[b][2], dis[b][3]);
}

void read(){
    cin >> numNode >> numEdge >> s >> t >> a >> b;
    FOR (i, 1, numEdge){
        static int u, v, cost;
        cin >> u >> v >> cost;
        edge[u].eb(pii(v, cost));
        edge[v].eb(pii(u, cost));
    }
}

int main(){
    gogobruhbruh;
    file("main");
    int test = 1;
    // cin >> test;
    while (test--)
        read(),
        solve();
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:28:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:5: note: in expansion of macro 'file'
   79 |     file("main");
      |     ^~~~
commuter_pass.cpp:28:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:79:5: note: in expansion of macro 'file'
   79 |     file("main");
      |     ^~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 17608 KB Output is correct
2 Correct 176 ms 16216 KB Output is correct
3 Correct 167 ms 17360 KB Output is correct
4 Correct 161 ms 16340 KB Output is correct
5 Correct 159 ms 16288 KB Output is correct
6 Correct 184 ms 17612 KB Output is correct
7 Correct 165 ms 16336 KB Output is correct
8 Correct 162 ms 16332 KB Output is correct
9 Correct 165 ms 16840 KB Output is correct
10 Correct 140 ms 17116 KB Output is correct
11 Correct 53 ms 10764 KB Output is correct
12 Correct 180 ms 16848 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 17436 KB Output is correct
2 Correct 180 ms 16244 KB Output is correct
3 Correct 181 ms 17212 KB Output is correct
4 Correct 183 ms 16332 KB Output is correct
5 Correct 197 ms 16328 KB Output is correct
6 Correct 216 ms 16272 KB Output is correct
7 Correct 194 ms 17496 KB Output is correct
8 Correct 189 ms 16252 KB Output is correct
9 Correct 178 ms 16332 KB Output is correct
10 Correct 194 ms 16660 KB Output is correct
11 Correct 51 ms 11088 KB Output is correct
12 Correct 164 ms 16272 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7000 KB Output is correct
2 Correct 2 ms 5776 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 11 ms 7948 KB Output is correct
5 Correct 7 ms 7004 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Incorrect 2 ms 5980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 17608 KB Output is correct
2 Correct 176 ms 16216 KB Output is correct
3 Correct 167 ms 17360 KB Output is correct
4 Correct 161 ms 16340 KB Output is correct
5 Correct 159 ms 16288 KB Output is correct
6 Correct 184 ms 17612 KB Output is correct
7 Correct 165 ms 16336 KB Output is correct
8 Correct 162 ms 16332 KB Output is correct
9 Correct 165 ms 16840 KB Output is correct
10 Correct 140 ms 17116 KB Output is correct
11 Correct 53 ms 10764 KB Output is correct
12 Correct 180 ms 16848 KB Output is correct
13 Correct 189 ms 17436 KB Output is correct
14 Correct 180 ms 16244 KB Output is correct
15 Correct 181 ms 17212 KB Output is correct
16 Correct 183 ms 16332 KB Output is correct
17 Correct 197 ms 16328 KB Output is correct
18 Correct 216 ms 16272 KB Output is correct
19 Correct 194 ms 17496 KB Output is correct
20 Correct 189 ms 16252 KB Output is correct
21 Correct 178 ms 16332 KB Output is correct
22 Correct 194 ms 16660 KB Output is correct
23 Correct 51 ms 11088 KB Output is correct
24 Correct 164 ms 16272 KB Output is correct
25 Correct 7 ms 7000 KB Output is correct
26 Correct 2 ms 5776 KB Output is correct
27 Correct 2 ms 5980 KB Output is correct
28 Correct 11 ms 7948 KB Output is correct
29 Correct 7 ms 7004 KB Output is correct
30 Correct 2 ms 5980 KB Output is correct
31 Incorrect 2 ms 5980 KB Output isn't correct
32 Halted 0 ms 0 KB -