Submission #1266400

#TimeUsernameProblemLanguageResultExecution timeMemory
1266400abcdxyz123Toll (BOI17_toll)C++20
100 / 100
82 ms9736 KiB
#include<bits/stdc++.h> #define inf 1000000000 #define pi pair<int,int> #define fi first #define se second #define maxn 50002 #define maxk 7 using namespace std; int k,n,m,q; int dp[maxn][maxk]; vector<pi>in[maxn]; vector<pi>out[maxn]; int idb(int i) { return i/k; } int lb(int i) { return i*k; } int rb(int i) { return min(n-1,(i+1)*k-1); } struct node { int s,t,id; node(int s=0,int t=0,int id=0) { this->s=s; this->t=t; this->id=id; } }; int ans[maxn]; inline void ckmin(int &x,int y){if(x>y)x=y;} void dnc(int l,int r,vector<node>&Query) { if(l>r)return ; if(l==r) { for(auto[s,t,id]:Query) { ans[id]=inf; } return; } int mid=(l+r)/2; for(int i=l;i<=r;i++) { for(int u=lb(i);u<=rb(i);u++) { for(int v=0;v<k;v++) { dp[u][v]=inf; } } } for(int u=lb(mid);u<=rb(mid);u++) { dp[u][u%k]=0; } for(int i=mid-1;i>=l;i--) { for(int u=lb(i);u<=rb(i);u++) { for(int t=0;t<k;t++) { for(auto[v,w]:out[u]) { ckmin(dp[u][t],dp[v][t]+w); } } } } for(int i=mid+1;i<=r;i++) { for(int u=lb(i);u<=rb(i);u++) { for(int t=0;t<k;t++) { for(auto[v,w]:in[u]) { ckmin(dp[u][t],dp[v][t]+w); } } } } vector<node>QueryL; vector<node>QueryR; for(auto[s,t,id]:Query) { if(idb(t)<mid)QueryL.push_back(node(s,t,id)); else if(idb(s)>mid)QueryR.push_back(node(s,t,id)); else { if(idb(s)==idb(t))ans[id]=inf; else { ans[id]=inf; for(int x=0;x<k;x++) { ckmin(ans[id],dp[s][x]+dp[t][x]); } } } } dnc(l,mid-1,QueryL); dnc(mid+1,r,QueryR); } int main() { ios::sync_with_stdio(false); 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; out[u].push_back({v,w}); in[v].push_back({u,w}); } vector<node>Query; for(int i=1;i<=q;i++) { int u,v; cin>>u>>v; if(idb(u)>=idb(v))ans[i]=inf; else { Query.push_back(node(u,v,i)); } } dnc(0,idb(n),Query); for(int i=1;i<=q;i++) { if(ans[i]==inf)cout<<-1<<'\n'; else cout<<ans[i]<<'\n'; } }
#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...