Submission #1123074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123074		ro9669	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	164 ms	23276 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;

int n , m , s , t , l; ll k;
vector<ii> g[maxN];
ll d[2][maxN];

void dijkstra(int id , int st){
    for (int i = 1 ; i <= n ; i++) d[id][i] = k + 1;
    d[id][st] = 0;
    priority_queue<lli , vector<lli> , greater<lli>> pq;
    pq.push({d[id][st] , st});
    while (pq.empty() == 0){
        auto it = pq.top(); pq.pop();
        int u = it.se;
        if (d[id][u] != it.fi) continue;
        for (auto e : g[u]){
            int v = e.fi;
            int w = e.se;
            if (d[id][v] > it.fi + 1ll * w){
                d[id][v] = it.fi + 1ll * w;
                pq.push({d[id][v] , v});
            }
        }
    }
}

vector<ll> val;

void solve(){
    cin >> n >> m >> s >> t >> l >> k;
    for (int i = 1 ; i <= m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    dijkstra(0 , s);
    dijkstra(1 , t);
    if (d[0][t] <= k){
        cout << 1ll * n * (n - 1) / 2 << "\n";
        return;
    }
    for (int i = 1 ; i <= n ; i++) val.push_back(d[1][i]);
    sort(all(val));
    ll ans = 0;
    for (int i = 1 ; i <= n ; i++){
        int x = upper_bound(all(val) , k - 1ll * l - d[0][i]) - val.begin();
        ans += 1ll * x;
    }
    cout << ans << "\n";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 29 / 29
• Subtask 4: 47 / 47