Submission #1319602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319602		nanaseyuzuki	Construction Project 2 (JOI24_ho_t2)	C++20	8 / 100	194 ms	29476 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, m, s, t, l, k, d[2][mn];
vector <pii> a[mn];
map <pii, int> mp;

void dijkstra(int st, int kc[]){
	fill(kc, kc + mn, inf);
	
	priority_queue <pii, vector <pii>, greater<pii>> pq;
	kc[st] = 0; pq.push({kc[st], st});

	while(pq.size()){
		auto [c, u] = pq.top(); pq.pop();
		if(c > kc[u]) continue;
			
		for(auto [v, w] : a[u]){
			if(kc[v] > kc[u] + w){
				kc[v] = kc[u] + w;
				pq.push({kc[v], v});
			}
		}
	}
}

void solve() {
    cin >> n >> m >> s >> t >> l >> k;
    for(int i = 1; i <= m; i++){
    	int u, v, c; cin >> u >> v >> c;
    	a[u].push_back({v, c});
    	a[v].push_back({u, c});
    }

    dijkstra(s, d[0]); dijkstra(t, d[1]);

    if(d[0][t] <= k){
    	cout << n * (n - 1) / 2 << '\n';
    	return;
    }

    vector <int> val;
    for(int i = 1; i <= n; i++) val.push_back(d[1][i]);
   	sort(all(val));

  	int res = 0;
  	for(int i = 1; i <= n; i++){
  		int kc = k - d[0][i] - l;
  		debug(kc, *upper_bound(all(val), kc));
  		res += upper_bound(all(val), kc) - val.begin();
  	}
  	cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #define task "Kawabata"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

Compilation message (stderr)

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

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