Submission #992131

#	Time	Username	Problem	Language	Result	Execution time	Memory
992131		8pete8	Construction Project 2 (JOI24_ho_t2)	C++17	100 / 100	181 ms	30212 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<cassert>
#include<limits.h>
#include<cmath>
#include<set>
#include<numeric> //gcd(a,b)
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
const int mod=998244353,mxn=2e5+5,lg=30,inf=1e18,minf=-1e9,Mxn=100000,root=700;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int n,m;
vector<pii>adj[mxn+10];
vector<pii> dijk(int st){
	vector<pii>dist(n,{inf,0});
	for(int i=1;i<n;i++)dist[i].s=i;
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	dist[st].f=0;
	pq.push({0,st});
	while(!pq.empty()){
		int cost=pq.top().f,cur=pq.top().s;
		pq.pop();
		if(cost!=dist[cur].f)continue;
		for(auto i:adj[cur])if(dist[i.f].f>dist[cur].f+i.s){
			dist[i.f].f=dist[cur].f+i.s;
			pq.push({dist[i.f].f,i.f});
		}
	}
	return dist;
}
struct fen{
	int fwk[mxn+10];
	void update(int pos,int val){for(int i=pos+1;i<=n+1;i+=(i&-i))fwk[i]+=val;}
	int qry(int pos){
		int sum=0;
		for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
		return sum;
	}
}t;
int32_t main(){
	fastio
	cin>>n>>m;
	int st,ed,l,k;cin>>st>>ed>>l>>k;
	st--;
	ed--;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		--a;
		--b;
		adj[a].pb({b,c});
		adj[b].pb({a,c});
	}
	vector<pii>d1=dijk(st),d2=dijk(ed);
	if(d1[ed].f<=k){
		cout<<(n*(n-1))/2;
		return 0;
	}
	sort(rall(d1));
	for(int i=0;i<d1.size();i++)d2[d1[i].s].s=i;
	sort(all(d2));
	int cur=0;
	int ans=0;
	for(int i=0;i<d1.size();i++){
		int need=k-d1[i].f-l;
		while(cur<d2.size()&&d2[cur].f<=need){
			t.update(d2[cur].s,1);
			cur++;
		}
		ans+=t.qry(i);
	}
	cout<<ans;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:86:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=0;i<d1.size();i++)d2[d1[i].s].s=i;
      |              ~^~~~~~~~~~
Main.cpp:90:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0;i<d1.size();i++){
      |              ~^~~~~~~~~~
Main.cpp:92:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(cur<d2.size()&&d2[cur].f<=need){
      |         ~~~^~~~~~~~~~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:36:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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