제출 #244634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
244634		TheLorax	Toll (BOI17_toll)	C++11	0 / 100	87 ms	12156 KiB

toll

#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);
  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;
    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]);
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44