oj.uz

Submission #244643

# Submission time Handle Problem Language Result Execution time Memory
244643 2020-07-04T13:26:47 Z TheLorax Toll (BOI17_toll) C++11
0 / 100
 81 ms 12032 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")

#define F first
#define S second
#define MT make_tuple
#define MP make_pair
#define SZ(a) ((int)(a).size())
#define PB push_back
#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i)+1)
#define PAR(i) ((i)/2)
#define ALL(a) (a).begin(), (a).end()
#define END(s) {cout << s;return;}

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;

int main(){
  int k, n, m, o;
  scanf("%d %d %d %d", &k,&n,&m,&o);
  n=k*((n+k-1)/k);
  int lgn=0;
  while ((1<<lgn)*k<n)
    lgn++;
  ll dis[n][k][lgn];
  for(int i=0; i<n; i++)
    for(int j=0; j<k; j++)
      for(int l=0; l<lgn; l++)
        dis[i][j][l]=INT_MAX*10LL;
  for(int i=0; i<m; i++){
    int a, b, t; scanf("%d %d %d", &a, &b, &t);
    dis[a][b%5][0]=t;
  }
  for(int l=1; l<lgn; l++)
    for(int i=0; i<n; i++)
      for(int j=0; j<k; j++)
        for(int p=0; p<k; p++)
          if(p+k*(i/k+(1<<(l-1)))<n)
            dis[i][j][l]=min(dis[i][j][l], dis[i][p][l-1]+dis[p+k*(i/k+(1<<(l-1)))][j][l-1]);
  for(int q=0; q<o; q++){
    int a, b; scanf("%d %d", &a, &b);
    int d=b/k-a/k;
    if(d<1){
      printf("-1\n");
      continue;
    }
    std::vector<ll> t(k, INT_MAX*10LL), t2(k,INT_MAX*10LL);
    t2[a%k]=0;
    a-=a%k;
    for(int i=20; i>=0; i--){
      if(!((1<<i)&d))
        continue;
      for(int j=0; j<k; j++)
        for(int p=0; p<k; p++)
          t[j]=min(t[j], t2[p]+dis[p+a][j][i]);
      a+=(1<<i)*k;
      for(int j=0; j<k; j++){
        t2[j]=t[j];
        t[j]=INT_MAX*10LL;
      }
    }
    if(t2[b%k]>INT_MAX)
      t2[b%k]=-1;
    printf("%lld\n", t2[b%k]);
  }
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &k,&n,&m,&o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:36:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int a, b, t; scanf("%d %d %d", &a, &b, &t);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:46:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int a, b; scanf("%d %d", &a, &b);
               ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 12032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -