oj.uz

Submission #945151

# Submission time Handle Problem Language Result Execution time Memory
945151 2024-03-13T12:51:49 Z Xiaoyang Commuter Pass (JOI18_commuter_pass) C++17
15 / 100
 2000 ms 52540 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
 
#define fi first 
#define se second 
#define pll pair<ll,ll>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl;
#define MP make_pair
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define endl "\n"
const ll inf=1e18;
ll lowbit(ll x){return x&(-x);}


const ll maxn=1e5+5;
map<pll,bool>mp;
vector<pll>alist[maxn];
ll st[maxn],uv[maxn];
ll n,m;
ll s,t;
ll u,v;

void dfs(ll uu){
	for(auto x:alist[uu]){
		if(st[x.se]>st[uu])continue;
		if(st[x.se]+x.fi==st[uu]){
			mp[MP(x.se,uu)]=1;
			mp[MP(uu,x.se)]=1;
			dfs(x.se);
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,m;cin>>n>>m;
	ll s,t;cin>>s>>t;
	ll u,v;cin>>u>>v;
	rep(i,0,m){
		ll a,b,c;cin>>a>>b>>c;
		alist[a].pb(MP(c,b));
		alist[b].pb(MP(c,a));
	}
	
	memset(st,63,sizeof st);
	st[s]=0;
	priority_queue<pll,vector<pll>,greater<pll>>q;
	q.push(MP(0ll,s));
	while(!q.empty()){
		auto uu=q.top();
		q.pop();
		if(uu.fi!=st[uu.se])continue;
		for(auto x:alist[uu.se]){
			if(uu.fi+x.fi<st[x.se]){
				st[x.se]=uu.fi+x.fi;
				q.push(MP(st[x.se],x.se));
			}
		}
	}
	dfs(t);
	
	//for(auto xx:mp)cout<<xx.fi.fi<<" "<<xx.fi.se<<endl;
	
	memset(uv,63,sizeof uv);
	uv[u]=0;
	while(!q.empty())q.pop();
	q.push(MP(0ll,u));
	while(!q.empty()){
		auto uu=q.top();
		q.pop();
		if(uu.fi!=uv[uu.se])continue;
		for(auto x:alist[uu.se]){
			if(mp[MP(x.se,uu.se)])x.fi=0;
			//debug(x.fi);
			//debug(x.se);
			//debug(uu.fi);
			if(uu.fi+x.fi<uv[x.se]){
				uv[x.se]=uu.fi+x.fi;
				q.push(MP(uv[x.se],x.se));
			}
		}
	}
	//rep(i,1,n+1)cout<<uv[i]<<" ";
	//cout<<endl;
	cout<<uv[v]<<endl;
	return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 44220 KB Output is correct
2 Execution timed out 2045 ms 19908 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 47588 KB Output is correct
2 Correct 427 ms 47684 KB Output is correct
3 Correct 410 ms 47244 KB Output is correct
4 Correct 458 ms 47528 KB Output is correct
5 Correct 426 ms 48584 KB Output is correct
6 Correct 459 ms 51648 KB Output is correct
7 Correct 524 ms 52540 KB Output is correct
8 Correct 407 ms 47816 KB Output is correct
9 Correct 420 ms 48552 KB Output is correct
10 Correct 409 ms 47160 KB Output is correct
11 Correct 163 ms 31824 KB Output is correct
12 Correct 426 ms 51928 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2021 ms 5724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 44220 KB Output is correct
2 Execution timed out 2045 ms 19908 KB Time limit exceeded
3 Halted 0 ms 0 KB -