oj.uz

Submission #446468

# Submission time Handle Problem Language Result Execution time Memory
446468 2021-07-22T04:44:27 Z anmolagarwal Commuter Pass (JOI18_commuter_pass) C++17
31 / 100
 335 ms 22412 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; // trick to explore an implicit 2D grid
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // S,SE,E,NE,N,NW,W,SW neighbors  //GO FOR EVEN FOR 4 moves
char ch[] = {'U', '!', 'L', '!', 'D', '!', 'R', '!'};
#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

const int M = 1e5 + 1;
vector<pair<LL, int>> adj[M];
LL n;
const LL INF = LONG_LONG_MAX;
vector<LL> d_algo(int src)
{
    vector<LL> dis(n + 1, INF);
    vector<bool> processed(n + 1, false);
    using T = pair<LL, int>;
    priority_queue<T, vector<T>, greater<>> q;
    dis[src] = 0;
    q.push({0, src});
    while (!q.empty())
    {
        auto ptr = q.top();
        LL node, dis_now;
        tie(dis_now, node) = ptr;
        q.pop();
        if (processed[node])
        {
            continue;
        }
        processed[node] = true;
        for (const auto &x : adj[node])
        {
            int c = x.first;
            LL wt = x.second;
            LL poss = wt + dis_now;
            if (poss < dis[c])
            {
                dis[c] = poss;
                q.push({dis[c], c});
            }
        }
    }
    return dis;
}
int main()
{
    fastinput;
    LL m, i, j, tc, k;
    //messi

    cin >> n >> m;
    LL src1, src2, dest1, dest2;
    cin >> src1 >> dest1;
    cin >> src2 >> dest2;

    while (m--)
    {
        cin >> i >> j >> k;
        adj[i].pb({j, k});
        swap(i, j);
        adj[i].pb({j, k});
    }

    vector<LL> dis1 = d_algo(src1);
    vector<LL> dis2 = d_algo(dest1);

    ///////////////////////////////////////
    int src = src2;
    vector<LL> dis(n + 1, INF);
    vector<bool> processed(n + 1, false);
    using T = pair<LL, int>;
    priority_queue<T, vector<T>, greater<>> q;
    dis[src] = 0;
    q.push({0, src});

    auto nice = [&](int n1, int n2, LL wt)
    {
        if (dis1[n1] + dis2[n2] + wt == dis1[dest1])
        {
            return true;
        }

        swap(n1, n2);
        if (dis1[n1] + dis2[n2] + wt == dis1[dest1])
        {
            return true;
        }
        return false;
    };
    while (!q.empty())
    {
        auto ptr = q.top();
        LL node, dis_now;
        tie(dis_now, node) = ptr;
        q.pop();
        if (processed[node])
        {
            continue;
        }
        processed[node] = true;
        for (const auto &x : adj[node])
        {
            int c = x.first;
            LL wt = x.second;
            if (nice(node, c, wt))
            {
                wt = 0;
            }
            LL poss = wt + dis_now;
            if (poss < dis[c])
            {
                dis[c] = poss;
                q.push({dis[c], c});
            }
        }
    }
    /////////////////////////////////////////
    // debug(dis[dest2]);

    // for (i = 1; i <= n; i++)
    // {
    //     cout << "dis " << i << " = " << dis[i] << endl;
    // }

    cout << dis[dest2] << endl;
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:59:17: warning: unused variable 'tc' [-Wunused-variable]
   59 |     LL m, i, j, tc, k;
      |                 ^~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 22400 KB Output is correct
2 Correct 319 ms 20928 KB Output is correct
3 Correct 294 ms 21328 KB Output is correct
4 Correct 314 ms 21276 KB Output is correct
5 Correct 299 ms 20668 KB Output is correct
6 Correct 304 ms 22412 KB Output is correct
7 Correct 300 ms 20632 KB Output is correct
8 Correct 314 ms 20720 KB Output is correct
9 Correct 335 ms 21572 KB Output is correct
10 Correct 278 ms 21516 KB Output is correct
11 Correct 128 ms 12268 KB Output is correct
12 Correct 309 ms 21404 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 22176 KB Output is correct
2 Correct 324 ms 20948 KB Output is correct
3 Correct 306 ms 21908 KB Output is correct
4 Correct 314 ms 20868 KB Output is correct
5 Correct 311 ms 21016 KB Output is correct
6 Correct 297 ms 20992 KB Output is correct
7 Correct 302 ms 21848 KB Output is correct
8 Correct 305 ms 20900 KB Output is correct
9 Correct 310 ms 21912 KB Output is correct
10 Correct 303 ms 20876 KB Output is correct
11 Correct 143 ms 12348 KB Output is correct
12 Correct 291 ms 21156 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4428 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Incorrect 2 ms 2636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 22400 KB Output is correct
2 Correct 319 ms 20928 KB Output is correct
3 Correct 294 ms 21328 KB Output is correct
4 Correct 314 ms 21276 KB Output is correct
5 Correct 299 ms 20668 KB Output is correct
6 Correct 304 ms 22412 KB Output is correct
7 Correct 300 ms 20632 KB Output is correct
8 Correct 314 ms 20720 KB Output is correct
9 Correct 335 ms 21572 KB Output is correct
10 Correct 278 ms 21516 KB Output is correct
11 Correct 128 ms 12268 KB Output is correct
12 Correct 309 ms 21404 KB Output is correct
13 Correct 306 ms 22176 KB Output is correct
14 Correct 324 ms 20948 KB Output is correct
15 Correct 306 ms 21908 KB Output is correct
16 Correct 314 ms 20868 KB Output is correct
17 Correct 311 ms 21016 KB Output is correct
18 Correct 297 ms 20992 KB Output is correct
19 Correct 302 ms 21848 KB Output is correct
20 Correct 305 ms 20900 KB Output is correct
21 Correct 310 ms 21912 KB Output is correct
22 Correct 303 ms 20876 KB Output is correct
23 Correct 143 ms 12348 KB Output is correct
24 Correct 291 ms 21156 KB Output is correct
25 Correct 11 ms 4428 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Incorrect 2 ms 2636 KB Output isn't correct
28 Halted 0 ms 0 KB -