Submission #1163580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163580		shraefkt	Construction Project 2 (JOI24_ho_t2)	C++20	53 / 100	2096 ms	47128 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 200007;
const int INF = LLONG_MAX;
vector <pair<int,int>> adjlist[MAX]; // {weight,node}
//return distance, node
vector <pair<int,int>> dijkstra(int source, int x) { // find nodes with distance less than or equal to x from source
	int dist[MAX];
	fill(dist,dist+MAX-1,INF);
	priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,source});
	vector<pair<int,int>> candidates;
	while (!pq.empty()) {
		int d = pq.top().first;
		int n = pq.top().second;
		if (d>x) break;
		pq.pop();
		if (dist[n] != INF) continue;
		dist[n] = d;
		candidates.push_back({d,n});
		for (int i=0;i<adjlist[n].size();i++) {
			int v = adjlist[n][i].first; // neighbour
			int u = adjlist[n][i].second; // neighbour weight
			if (dist[v] == INF) {
				pq.push({dist[n] + u,v});
			}
		}
	}
	return candidates;
}
struct CompareByFirst {
    bool operator()(const pair<int,int> &a, const pair<int,int> &b) const {
        return a.first < b.first;
    }
};
int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N,M,S,T,L,K;
	cin >> N >> M >> S >> T >> L >> K;
	int a,b,c;
	for (int i=0;i<M;i++) {
		cin >> a >> b >> c;
		adjlist[a].push_back({b,c});
		adjlist[b].push_back({a,c});
	}
	
	//run dijkstra twice
	vector <pair<int,int>> from_source;
	from_source = dijkstra(S,K);
	for (auto &pair: from_source) {
		if (pair.second == T) {
			cout << (N) * (N-1) / 2;
			return 0;
			}
		}
	/*
	for (auto &z: from_source) {
		cout << z.first << " " << z.second << endl;
	}
	cout << "-----" << endl;
	*/
	vector <pair<int,int>> to_source = dijkstra(T,K-L);
	/*
	for (auto &z: to_source) {
		cout << z.first << " " << z.second << endl;
	}
	cout << "-----" << endl;
	*/
	multiset<pair<int,int>,CompareByFirst> from_ms;
	from_ms.insert(from_source.begin(),from_source.end());
	multiset<pair<int,int>> to_ms;
	to_ms.insert(to_source.begin(),to_source.end());
	int count = 0;
	for (auto &candidate: to_ms) {
		//cout << candidate.first << endl;
		auto it = from_ms.upper_bound({K - L - candidate.first, INF});
		if (it == from_ms.end()) {
			count += from_ms.size();
			continue;
		}
		int t = distance(from_ms.begin(), it);
		//cout <<  t << endl;
		count += t;
		}
	cout << count;


}

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