Submission #1109631

#TimeUsernameProblemLanguageResultExecution timeMemory
1109631theSkeletonToll (BOI17_toll)C++17
0 / 100
45 ms31052 KiB
//!!in the name of god!! #include<bits/stdc++.h> #define space <<' '<< #define endl '\n' #define inf 1e9 #define F first #define S second #define PB push_back #define PF push_front #define pll pair<ll,ll> #define pii pair<int,int> #define md(a) ((a+mod)%mod) #define MP(a,b) make_pair(a,b) #define all(a) a.begin(),a.end() #define MT(a,b,c) make_tuple(a,b,c) typedef long long ll; using namespace std; template<typename t> using heap= priority_queue<t,vector<t>,greater<t>>; const int mx = 5e4+5; const int lg = 22; vector<pll> adj[mx][lg]; int glg(int v){ if(v<2)return 0; return glg(v/2)+1; } int has(vector<pll>& q,int s){ for(int t=0;t<q.size();t++) if(q[t].F==s)return t; return -1; } int main(){ std::ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int k,n,m,o; cin>>k>>n>>m>>o; for(int u,v,t;m--;) cin>>u>>v>>t, adj[u][0].PB(MP(v,t)); for(int v=0;v<n;v++) for(int p=1;p<lg;p++) for(auto e:adj[v][p-1]) for(auto d:adj[e.F][p-1]){ int c=has(adj[v][p],d.F); if(c!=-1)adj[v][p][c] =min(adj[v][p][c],MP(d.F,e.S+d.S)); else adj[v][p].PB(MP(d.F,e.S+d.S)); } for(int a,b;o--;){ cin>>a>>b; int c=a/k,e=b/k; vector<pll> cu,te; cu.PB(MP(a,0)); while(c<e){ te.clear(); int p=glg(e-c); for(auto e:cu) for(auto d:adj[e.F][p]){ int t=has(te,d.F); if(t!=-1)te[t]=min(te[t],MP(d.F,e.S+d.S)); else te.PB(MP(d.F,e.S+d.S)); } c+=1<<p; cu=te; } int t=has(cu,b); if(t==-1) cout<<-1<<endl; else cout<<cu[t].S<<endl; } }

Compilation message (stderr)

toll.cpp: In function 'int has(std::vector<std::pair<long long int, long long int> >&, int)':
toll.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int t=0;t<q.size();t++)
      |                 ~^~~~~~~~~
#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...