Submission #1101921

#TimeUsernameProblemLanguageResultExecution timeMemory
1101921doducanhToll (BOI17_toll)C++14
100 / 100
276 ms250952 KiB
///breaker #pragma GCC optimize("O2") #include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define ii pair<int,int> #define mp make_pair #define in(x) freopen(x,"r",stdin) #define out(x) freopen(x,"w",stdout) #define bit(x,i) ((x>>i)&1) #define lc (id<<1) #define rc ((id<<1)^1) const int maxn=5e4+7; const int inf=1e9+7; vector<ii>adj[maxn]; int k,n,m,q; int dp[maxn][25][5][5]; void mix(int target[5][5],int a[5][5],int b[5][5]){ for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ for(int k=0;k<5;k++){ target[i][j]=min(target[i][j],a[i][k]+b[k][j]); } } } } void sol(void){ cin>>k>>n>>m>>q; memset(dp,inf,sizeof(dp)); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; adj[u].push_back({v,w}); dp[u/k][0][u%k][v%k]=w; } for(int i=1;i<=20;i++){ for(int j=0;j+(1<<i)<n;j++){ mix(dp[j][i],dp[j][i-1],dp[j+(1<<(i-1))][i-1]); } } while(q--){ int u,v; cin>>u>>v; int ans[5][5]; int tmp[5][5]; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ if(i==j)ans[i][j]=0; else ans[i][j]=inf; } } for(int left=u/k,right=v/k,i=20;i>=0;i--)if(left+(1<<i)<=right){ for(int j=0;j<5;j++){ for(int k=0;k<5;k++){ tmp[j][k]=ans[j][k]; ans[j][k]=inf; } } mix(ans,tmp,dp[left][i]); left+=(1<<i); } cout<<(ans[u%k][v%k]==inf?-1:ans[u%k][v%k])<<"\n"; } } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; while(t--){ sol(); } // you should actually read the stuff at the bottom return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */
#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...