oj.uz

Submission #1035732

# Submission time Handle Problem Language Result Execution time Memory
1035732 2024-07-26T14:15:50 Z borisAngelov Construction Project 2 (JOI24_ho_t2) C++17
0 / 100
 3 ms 5464 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const long long inf = (1LL << 62);

int n, m, s, t;
long long L, K;

long long ds[maxn], dt[maxn];
pair<long long, long long> d[maxn];

vector<pair<int, int>> g[maxn];

void dijkstra(int start, long long dist[])
{
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;
    pq.push({0, start});
    dist[start] = 0;

    while (!pq.empty())
    {
        auto top = pq.top();
        pq.pop();

        int node = top.second;
        long long curr = -top.first;

        for (int i = 0; i < g[node].size(); ++i)
        {
            if (dist[g[node][i].first] > curr + g[node][i].second)
            {
                dist[g[node][i].first] = curr + g[node][i].second;
                pq.push({-dist[g[node][i].first], g[node][i].first});
            }
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m >> s >> t >> L >> K;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    dijkstra(s, ds);
    dijkstra(t, dt);

    if (ds[t] <= K)
    {
        cout << ((1LL * n) * (1LL * (n - 1))) / 2 << endl;
        return 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        d[i] = {ds[i], dt[i]};
    }

    sort(d + 1, d + n + 1);

    long long ans = 0;

    for (int i = 2; i <= n; ++i)
    {
        int l = 1;
        int r = i - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (d[i].second + d[mid].first <= K - L)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        ans += r;
    }

    cout << ans << endl;

    return 0;
}

Compilation message

Main.cpp: In function 'void dijkstra(int, long long int*)':
Main.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 3 ms 5464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5168 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5164 KB Output is correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5168 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 5164 KB Output is correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Incorrect 3 ms 5464 KB Output isn't correct
6 Halted 0 ms 0 KB -