oj.uz

Submission #1059870

# Submission time Handle Problem Language Result Execution time Memory
1059870 2024-08-15T08:47:29 Z anango Construction Project 2 (JOI24_ho_t2) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int INF = 1LL<<61;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;


signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
       // freopen("output.txt", "w", stdout);
    #endif
    #ifndef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif //fast IO
    int n,m; cin >> n >> m;
    int S,T,L,K; cin >> S >> T >> L >> K; S--; T--;
    vector<vector<pair<int,int>>> adjlist(n);
    for (int i=0; i<m; i++) {
        int u,v,w; cin >> u >> v >> w; u--; v--;
        adjlist[u].push_back({v,w}); adjlist[v].push_back({u,w});
    }
    vector<int> distS(n,INF);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> vals;
    distS[S] = 0; 
    for (int i=0; i<n; i++) {
        vals.push({distS[i],i});
    }
    while (vals.size()) {
        pair<int,int> fir = vals.top(); vals.pop();
        int u = fir.second; int dis = fir.first;
        if (dis>distS[u]) continue;
        for (pair<int,int> j:adjlist[u]) {
            if (dis+j.second<distS[j.first]) {
                vals.push({dis+j.second,j.first});
                distS[j.first] = dis+j.second;
            }
        }
    }

    vector<int> distT(n,INF);
    distT[T] = 0; 
    for (int i=0; i<n; i++) {
        vals.push({distT[i],i});
    }
    while (vals.size()) {
        pair<int,int> fir = vals.top(); vals.pop();
        int u = fir.second; int dis = fir.first;
        if (dis>distT[u]) continue;
        for (pair<int,int> j:adjlist[u]) {
            if (dis+j.second<distT[j.first]) {
                vals.push({dis+j.second,j.first});
                distT[j.first] = dis+j.second;
            }
        }
    }

    if (distS[T]<=K) {
        cout << n*(n-1)/2 << endl;
        return 0;
    }
    vector<int> s_sorted;
    for (int i=0; i<n; i++) {
        s_sorted.push_back(i);
    }
    sort(s_sorted.begin(), s_sorted.end(), [&](const int i1, const int i2) {
        return distS[i1]>distS[i2];
    }); //descending order to ensure distS[v]>distS[u]

    ordered_set distv;
    int su = 0;
    for (int i=0; i<n; i++) {
        int u =  s_sorted[i];
        int max_poss_weight = K-L-distS[u];
        su+=distv.order_of_key(max_poss_weight+1);

        distv.insert(distT[u]);
    }
    cout << su << endl;

    
    for (int i=0; i<n; i++) {
        //cout << i <<" " << distS[i] << " " << distT[i] << endl;
    }
    
}

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 16.0

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

Subtask #3
0.0 / 29.0

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

Subtask #4
0.0 / 47.0

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