Submission #1259867

#TimeUsernameProblemLanguageResultExecution timeMemory
1259867nguyenhuythachToll (BOI17_toll)C++20
0 / 100
70 ms87620 KiB
#include<bits/stdc++.h> #include<algorithm> #include<random> #include<chrono> #include<cstdlib> #include<ctime> #include<numeric> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<iomanip> #define int long long #define ll long long #define L LLONG_MAX #define fi first #define se second #define pii pair<int,int> #define sz(a) ((int)a.size()) #define FOR(i,j,k) for(int i=j;i<=k;i++) #define REP(i,k,j) for(int i=k;i>=j;i--) #define FORD(i,a) for(auto i:a) #define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(l,r) ((l)+(rng()%(r-l+1))) using namespace std; const int nmax=5e4+69; int n,m,k,q; vector<pii> adj[nmax]; vector<pii> rev[nmax]; int suf[17][nmax][6],pfx[17][nmax][6]; void input() { cin >> k >> n >> m >> q; FOR(i,1,m) { int u,v,w; cin >> u >> v >> w; u++; v++; adj[u].push_back({v,w}); rev[v].push_back({u,w}); } } pii pos(int x) { return {(x-1)/k+1,(x-1)%k+1}; } void dnc(int l,int r,int lv) { if(pos(l).fi==pos(r).fi || l>=r) return; int mid=(l+r)/2; //precase int sl=mid,sr=mid; while(pos(sl).fi==pos(mid).fi && sl>1) sl--; while(pos(sr).fi==pos(mid).fi && sr<n) sr++; FOR(i,sl,sr) suf[lv][i][pos(i).se]=0; FOR(i,sl,sr) pfx[lv][i][pos(i).se]=0; //build REP(u,sl,l) { FORD(i,adj[u]) { FOR(j,1,k) { if(suf[lv][i.fi][j]!=L) suf[lv][u][j]=min(suf[lv][u][j],suf[lv][i.fi][j]+i.se); } } } FOR(u,sr,r) { FORD(i,rev[u]) { FOR(j,1,k) { if(pfx[lv][i.fi][j]!=L) pfx[lv][u][j]=min(pfx[lv][u][j],pfx[lv][i.fi][j]+i.se); } } } //recursion dnc(l,mid-1,lv+1); dnc(mid+1,r,lv+1); } pii find(int l,int r,int lv,int lf,int rt) { int mid=(l+r)/2; if(l<=lf && rt<=r && lf<=mid && mid<=rt) return {lv,mid}; if(l<=lf && rt<=mid) return find(l,mid,lv+1,lf,rt); else return find(mid+1,r,lv+1,lf,rt); } void solve() { //preprocess FOR(i,0,16) FOR(j,1,n) FOR(k,1,5) { suf[i][j][k]=L; pfx[i][j][k]=L; } dnc(1,n,1); // FOR(lv,1,4) {FOR(i,1,n) {FOR(j,1,k) cout << suf[lv][i][j] << ' '; cout << '\n';} cout << '\n';} //query while(q--) { int l,r; cin >> l >> r; l++; r++; pii save=find(1,n,1,l,r); int mid=save.se; int lv=save.fi; int ans=L; if(pos(l).fi+1==pos(r).fi) { FORD(i,adj[l]) if(i.fi==r) ans=i.se; } else { FOR(i,1,k) if(suf[lv][l][i]!=L && pfx[lv][r][i]!=L) ans=min(ans,suf[lv][l][i]+pfx[lv][r][i]); } if(ans==L) cout << -1 << '\n'; else cout << ans << '\n'; } } signed main() { //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); input(); solve(); }
#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...