Submission #1248737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248737		Bui_Quoc_Cuong	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	323 ms	53960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int numNode, numEdge, sour, fin, bonusLen;
long long targetLen;

vector <array <int, 2>> G[N];

int maxWei = 0;

void init(){
	cin >> numNode >> numEdge >> sour >> fin >> bonusLen >> targetLen;
	for(int i = 1; i <= numEdge; i++){
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({v, w}); G[v].push_back({u, w});
		maxWei = max(w, maxWei);
	}
	maxWei = max(maxWei, bonusLen);
	maxWei *= 2;
}

namespace sub1{
	long long dist1[N], dist2[N];

	void dijk(int sour, long long dist[]){
		#define bg array <long long, 2>
		priority_queue <bg, vector <bg>, greater <bg>> pq;
		for(int i = 1; i <= numNode; i++){
			dist[i] = 1e18;
		}
		pq.push({dist[sour] = 0, sour});

		while(!pq.empty()){
			long long cost = pq.top()[0];
			int u = pq.top()[1];
			pq.pop();
			if(cost > dist[u]) continue;
			for(const array <int, 2> it : G[u]){
				int v = it[0], w = it[1];
				if(dist[v] > cost + w){
					dist[v] = cost + w;
					pq.push({dist[v], v});
				}
			}
		}
	}

	void solve(){
		dijk(sour, dist1); dijk(fin, dist2);
		bool check = dist1[fin] <= targetLen;
		if(check){
			cout << 1LL * numNode * (numNode - 1) / 2;
			return;
		}		
		int ans = 0;
		for(int u = 1; u <= numNode; u++){
			for(int v = u + 1; v <= numNode; v++){
				if(dist1[u] + bonusLen + dist2[v] <= targetLen){
					ans++;
				} 
				if(dist1[v] + bonusLen + dist2[u] <= targetLen){
					ans++;
				}
			}	
		}
		cout << ans;
	}
}

namespace sub2{
	long long dist1[N], dist2[N];

	void dijk(int sour, long long dist[]){
		#define bg array <long long, 2>
		priority_queue <bg, vector <bg>, greater <bg>> pq;
		for(int i = 1; i <= numNode; i++){
			dist[i] = 1e18;
		}
		pq.push({dist[sour] = 0, sour});

		while(!pq.empty()){
			long long cost = pq.top()[0];
			int u = pq.top()[1];
			pq.pop();
			if(cost > dist[u]) continue;
			for(const array <int, 2> it : G[u]){
				int v = it[0], w = it[1];
				if(dist[v] > cost + w){
					dist[v] = cost + w;
					pq.push({dist[v], v});
				}
			}
		}
	}

	struct FenwickTree{
		int bit[N];

		void up(int u, int val){
			for(int i = u; i <= 2 * numNode + 3; i+= i&-i) bit[i]+= val;
		}

		int get(int u){
			int sum = 0;
			for(int i = u; i; i-= i&-i) sum+= bit[i];
			return sum;
		}
	} fwt;

	void solve(){
		dijk(sour, dist1); dijk(fin, dist2);
		if(dist1[fin] <= targetLen){
			cout << 1LL * numNode * (numNode - 1) / 2;
			return;
		}
		targetLen-= bonusLen;

		vector <long long> values;
		values.push_back(targetLen);
		for(int i = 1; i <= numNode; i++){
			values.push_back(dist2[i]);
			values.push_back(targetLen - dist1[i]);
		}	
		sort(values.begin(), values.end());
		values.resize(unique(values.begin(), values.end()) - values.begin());

		map <long long, int> pos;
		for(int i = 0; i < (int)values.size(); i++) pos[values[i]] = i + 1;

		vector <int> sorted;
		for(int i = 1; i <= numNode; i++) sorted.push_back(i);
		sort(sorted.begin(), sorted.end(), [&](int u, int v){
			if(dist1[u] == dist1[v]) return dist2[u] < dist2[v];
			else return dist1[u] > dist1[v];
		});

		long long ans = 0;
		for(auto x : sorted){
			ans+= fwt.get(pos[targetLen - dist1[x]]);
			fwt.up(pos[dist2[x]], 1);
		}
		cout << ans;
	}
}

void process(){
	return sub2::solve();
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);   
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){ 
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

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

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