Submission #246849

#	Time	Username	Problem	Language	Result	Execution time	Memory
246849		kimbj0709	Toll (BOI17_toll)	C++14	0 / 100	793 ms	195060 KiB

toll

#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+220>=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+220>=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";*/
      for(int j=0;j<k;j++){
        for(int a=j;a<k;a++){
          assert(next[a]<=currdist[j]+dist[j+q*k][k*jump[k]+a]);
        }
      }
      /*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++){
               ~^~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44