Submission #696796

#TimeUsernameProblemLanguageResultExecution timeMemory
696796vjudge1Toll (BOI17_toll)C++17
0 / 100
541 ms223292 KiB
#include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> pii; #define fi first #define se second #define gcd __gcd #define endl '\n' const int N=200050,M=1000000007; const ll INF=1e18; struct matrix{ ll n, m; vector<vector<ll>> a; matrix(ll x, ll y, ll v=0){ n=x, m=y; a.assign(n, vector<ll>(m, v)); } auto & operator [](ll i){return a[i];} const auto & operator [](ll i)const{return a[i];} matrix()=default; matrix(const vector<vector<ll>> & x):a(x){ n=a.size(); m=a[0].size(); } friend ostream& operator <<(ostream& stream, const matrix &x){ for(auto i:x.a){ for(auto j:i) stream<<j<<" "; stream<<endl; } return stream; } static matrix identity(ll n){ matrix res(n, n); for(ll i=0; i<n; i++) res[i][i]=1; return res; } matrix operator *(const matrix b){ matrix a=*this, res(a.n, b.m, INF); // cout<<b<<a; for(ll i=0; i<a.n; i++) for(ll j=0; j<b.m; j++) for(ll k=0; k<a.m; k++) res[i][j]=min(res[i][j], a[i][k]+b[k][j]); // cout<<res<<"\n"; return res; } matrix pow(ll k){ matrix res=identity(this->n), a=*this; while(k){ if(k&1) res=res*a; a=a*a; k>>=1; } return res; } }; matrix p[N][16]; ll k, n, m, q, a, b, t; signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr); cin>>k>>n>>m>>q; for(ll i=0; i<n; i++) for(ll j=0; j<15; j++) p[i][j]=matrix(k, k, INF); while(m--){ cin>>a>>b>>t; if(a>b) swap(a, b); if(a/k+1==b/k){ // cout<<a<<" "<<b<<endl; p[a/k][0][a%k][b%k]=t; } } for(ll i=1; (1<<i)<n; i++) for(ll j=0; j+(1<<i)-1<=n; j++){ p[j][i]=p[j][i-1]*p[j+(1<<(i-1))][i-1]; } while(q--){ cin>>a>>b; ll now=a/k, l=b/k-a/k; bool bl=0; matrix res(k, k, INF); for(ll i=0; i<k; i++) res[i][i]=0; for(ll i=0; i<16; i++) if(l&(1<<i)){ res=p[now][i]*res; now+=i<<1; // cout<<res<<endl; bl=1; } // cout<<res<<endl; cout<<(res[a%k][b%k]==INF? -1: res[a%k][b%k])<<endl; } return 0; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:91:8: warning: variable 'bl' set but not used [-Wunused-but-set-variable]
   91 |   bool bl=0;
      |        ^~
#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...