Submission #1154799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154799		nguyenphong233	Construction Project 2 (JOI24_ho_t2)	C++20	100 / 100	156 ms	23724 KiB

Main

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define int long long
#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;

int n,m,s,t,l,k;
vector<ii> adj[MAX];
int dist[2][MAX];
int point[2];
priority_queue<ii,vector<ii>,greater<ii>> h;

void dijstra(bool c){
	h.push({0,point[c]});
	dist[c][point[c]] = 0;	
	while(!h.empty()){
		int u = h.top().Y;
		int d = h.top().X;
		h.pop();
		if(d != dist[c][u])continue;
		for(auto e : adj[u]){
			int v = e.X;
			int w = e.Y;
			if(dist[c][v] > dist[c][u] + w){
				dist[c][v] = dist[c][u] + w;
				h.push({dist[c][v],v});
			}
		}
	}
}
signed main(){
	
	read();
	cin >> n >> m >> s >> t >> l >> k;
	point[0] = s;
	point[1] = t;
	
	for(int i = 1;i <= n;i++){
		dist[0][i] = dist[1][i] = INF;
	}
	for(int i = 1,u,v,c;i <= m;i++){
		cin >> u >> v >> c;
		adj[u].push_back({v,c});
		adj[v].push_back({u,c});
	}	
	
	dijstra(0);
	dijstra(1);
	if(dist[1][s] <= k)return cout << (n * (n - 1) / 2),0;
	sort(dist[1] + 1,dist[1] + 1 + n);
	sort(dist[0] + 1,dist[0] + 1 + n);
	int id = n;
	int res = 0;
	for(int i = 1;i <= n;i++){
		while(id > 0 && dist[0][i] + l + dist[1][id] > k)id--;
		if(id == 0)break;
		res += id;
	}
	
	cout << res;
}

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