Submission #1093527

#TimeUsernameProblemLanguageResultExecution timeMemory
1093527DucNguyen2007Toll (BOI17_toll)C++14
7 / 100
34 ms10772 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=5e4+5,INF=1e9; const ll inf=2e18; int n,k,m,q,ans[maxN+1],d[maxN+1][7][2]; vector<pii> adj[maxN+1],adj_rv[maxN+1]; struct query { int l,r,id; }; vector<query> p; struct duongdi { int u,w; bool operator < (const duongdi &o)const { return w>o.w; } }; priority_queue<duongdi> pq; void clr(int l,int r,int id) { for(int i=l;i<=r;i++) { d[i][id][0]=d[i][id][1]=INF; } } void dijkstra(int s,int t,int type,int l,int r,vector<pii> adj[]) { d[s][t][type]=0; pq.push({s,0}); while(!pq.empty()) { duongdi tmp=pq.top(); int u=tmp.u,w=tmp.w; //cout<<u<<" "<<w<<'\n'; pq.pop(); if(d[u][t][type]<w) { continue; } for(auto [v,nw]:adj[u]) { if(v/k>r||v/k<l) { continue; } //cout<<v<<" "<<nw<<" "<<d[v][t][type]<<'\n'; if(d[v][t][type]>d[u][t][type]+nw) { d[v][t][type]=d[u][t][type]+nw; pq.push({v,d[v][t][type]}); } } } } void Dnc(int l,int r,vector<query> v) { if(v.empty()) { return; } if(l==r) { for(auto j:v) { ans[j.id]=0; } return; } int mid=(l+r)/2; for(int i=mid*k;i<(mid+1)*k;i++) { clr(l*k,(r+1)*k-1,i%k); dijkstra(i,i%k,0,l,mid,adj_rv); dijkstra(i,i%k,1,mid+1,r,adj); } vector<query> vec[2]; for(auto j:v) { if(j.l/k<=mid&&mid<j.r/k) { int tmp=INF; //cout<<l<<" "<<r<<" "<<j.l<<" "<<j.r<<'\n'; for(int i=0;i<k;i++) { tmp=min(tmp,d[j.l][i][0]+d[j.r][i][1]); //cout<<d[j.l][i][0]<<" "<<d[j.r][i][1]<<'\n'; } if(tmp==INF) { ans[j.id]=-1; } else ans[j.id]=tmp; } if(l<=j.l/k&&j.r/k<=mid) { vec[0].push_back(j); } if(mid<j.l/k&&j.r/k<=r) { vec[1].push_back(j); } } Dnc(l,mid,vec[0]); Dnc(mid+1,r,vec[1]); } int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>k>>n>>m>>q; for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); adj_rv[v].push_back({u,w}); } for(int i=1;i<=q;i++) { int l,r; cin>>l>>r; p.push_back({l,r,i}); } Dnc(0,n/k,p); for(int i=1;i<=q;i++) { cout<<ans[i]<<'\n'; } }

Compilation message (stderr)

toll.cpp: In function 'void dijkstra(int, int, int, int, int, std::vector<std::pair<int, int> >*)':
toll.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [v,nw]:adj[u])
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...