Submission #246890

#TimeUsernameProblemLanguageResultExecution timeMemory
246890eriksuenderhaufToll (BOI17_toll)C++11
100 / 100
1102 ms98548 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define f first #define s second #define sqrtn 230 #define maxn 50050 #define mxdist 500000000 vector<int> jump = {0,228,112,74,45,44}; int dist[maxn][231]; int k,no_of_vertex,no_of_edge,no_of_query; vector<int> top; vector<int> visited(maxn,0); vector<vector<pair<int,int> > > adj(maxn); vector<int> ipos(maxn,0); void topsort(int node){ visited[node] = 1; for(auto kk:adj[node]){ if(visited[kk.f]==1){ continue; } topsort(kk.f); } top.push_back(node); } void find(int node){ vector<pair<int,int> > curr; vector<int> distt(231,INT_MAX); for(int i=node;i<min(no_of_vertex,node+231);i++){ curr.push_back({ipos[i],i}); } distt[0] = 0; sort(curr.begin(),curr.end()); for(int i=0;i<curr.size();i++){ for(auto kk:adj[curr[i].s]){ if(kk.f>node+230){ continue; } distt[kk.f-node] = min(distt[kk.f-node],distt[curr[i].s-node]+kk.s); } } for(int i=0;i<231;i++){ dist[node][i] = INT_MAX; } for(int i=0;i<curr.size();i++){ dist[node][i] = distt[i]; } return; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> k >> no_of_vertex >> no_of_edge >> no_of_query; int input1,input2,input3; for(int i=0;i<no_of_edge;i++){ cin >> input1 >> input2 >> input3; adj[input1].push_back({input2,input3}); } for(int i=0;i<no_of_vertex;i++){ if(visited[i]==0){ topsort(i); } } reverse(top.begin(),top.end()); for(int i=0;i<top.size();i++){ ipos[top[i]] = i; } for(int i=0;i<no_of_vertex;i++){ find(i); } for(int i=0;i<no_of_query;i++){ cin >> input1 >> input2; vector<int> currdist(k,INT_MAX); if(input1+230>=input2){ if(dist[input1][input2-input1]>=INT_MAX){ cout << -1 << "\n"; } else{ cout << dist[input1][input2-input1] << "\n"; } continue; } int q = input1/k; q++; for(int j=0;j<k;j++){ currdist[j] = dist[input1][q*k+j-input1]; } while(1){ if(q*k+230>=input2){ int mini = INT_MAX; for(int j=0;j<k;j++){ mini = min(mini,dist[q*k+j][input2-q*k-j]+currdist[j]); } if(mini==INT_MAX){ cout << -1 << "\n"; } else{ cout << mini << "\n"; } break; } vector<int> next(k,INT_MAX); for(int j=0;j<k;j++){ /*for(int a=0;a<no_of_vertex;a++){ cout << dist[q*k+j][a] << " "; } cout << "\n-----------\n";*/ for(int a=0;a<k;a++){ //cout << dist[q*k+j][k*jump[k]+a] << "---\n"; //cout << j << " " << a << " " << dist[q*k+j][k*jump[k]+a-j] << " " << currdist[j] << " " << k*jump[k]+a << "\n"; next[a] = min(next[a],dist[q*k+j][k*jump[k]+a-j]+currdist[j]); } } /*for(int j=0;j<k;j++){ cout << next[j] << " "; } cout << "\n-----\n";*/ /*cout << q*k << "\n"; for(auto kk:next){ cout << kk << " "; } cout << endl;*/ currdist = next; q += jump[k]; } } }

Compilation message (stderr)

toll.cpp: In function 'void find(long long int)':
toll.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<curr.size();i++){
               ~^~~~~~~~~~~~
toll.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<curr.size();i++){
               ~^~~~~~~~~~~~
toll.cpp: In function 'int32_t main()':
toll.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<top.size();i++){
               ~^~~~~~~~~~~
#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...