Submission #1210755

#TimeUsernameProblemLanguageResultExecution timeMemory
1210755Younis_DwaiRobot (JOI21_ho_t4)C++20
0 / 100
255 ms31708 KiB
#pragma GCC optimize("O3,unroll-loops,Ofast") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define endl "\n" #define F first #define S second #define pb push_back #define pf push_front #define popf pop_frot #define popb pop_back #define int long long #define in insert #define mid (l+r)/2 //register int cnt using namespace std; const int N=1e5+5; int n,m,tree[N*8],d[N],vis[N]; vector<pair<int,int>> adj[N]; vector<pair<int,pair<int,int>>> E[N]; void upd(int node , int l , int r , int id , int v){ if(l==r){ tree[node]+=v; return ; } else if(id<=mid) upd(node*2,l,mid,id,v); else upd(node*2+1,mid+1,r,id,v); tree[node]=min(tree[node*2],tree[node*2+1]); return ; } int query(int node , int l , int r , int s , int e){ if(l>=s && r<=e) return tree[node]; else if(l>e || r<s) return 1e17; return min(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e)); } void dfs(int node){ vis[node]=1; if(E[node].size()>1) return ; for(auto u : E[node]){ if(vis[u.F]) continue ; dfs(u.F); } return ; } void Dijkstra(){ for(int i=1;i<=n;i++) d[i]=1e18; d[1]=0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; q.push({0,1}); while(!q.empty()){ int node=q.top().S,D=q.top().F; q.pop(); if(vis[node]) continue ; vis[node]=1; for(auto u : adj[node]){ if(d[u.F]>D+u.S){ d[u.F]=D+u.S; q.push({d[u.F],u.F}); } } } return; } int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(nullptr); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v,c,p; cin>>u>>v>>c>>p; E[u].pb({v,{c,p}}); E[v].pb({u,{c,p}}); } for(int i=1;i<=n;i++){ for(auto u : E[i]){ upd(1,1,m,u.S.F,u.S.S); } for(auto u : E[i]){ adj[i].pb({u.F,min(u.S.S+tree[1],query(1,1,m,u.S.F,u.S.F)-u.S.S)}); } for(auto u : E[i]){ upd(1,1,m,u.S.F,-u.S.S); } } if(m==1){ dfs(1); if(vis[n]) cout<<0; else cout<<-1; } else{ Dijkstra(); if(d[n]==1e18) cout<<-1; else cout<<d[n]; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...