제출 #380910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380910		leaked	Toll (BOI17_toll)	C++14	100 / 100	463 ms	209260 KiB

toll

#include <bits/stdc++.h>
//#include "debug.h"
////    #pragma GCC optimize("-O3")
////    #pragma GCC optimize("no-stack-protector")
////    #pragma GCC optimize("fast-math")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//    #pragma GCC target("avx,avx2,fma")
//    #pragma GCC optimization ("unroll-loops")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define f first
#define s second
#define se second
#define vec vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1ll<<x)
#define p_b push_back
#define m_p make_pair
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define sq(x) (x)*(x)
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
typedef pair<long long, long long> PII;
typedef pair<int, int> pii;
typedef long double ld;
typedef long long ll;
typedef pair<long long, long long > pll;
//template <typename T> umax(T &a, T b){return (a<b ? a=b,1 : 0);}
//template <typename T> umin(T &a, T b){return (a>b ? a=b,1 : 0);}
//typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> o_set;
const int N=5e4+1;
const int K=5;
const ll inf=1e18;
const ld eps = 1e-9;
const int ppp=73;
const int M=1e9+7;
const ll tx[4]={-1,1,0,0};
const ll ty[4]={0,0,-1,1};
const int lg=21;
const char rev_to[4]={'U','D','L','R'};
auto rnd=bind(uniform_int_distribution<ll>(1,1e9),mt19937(time(0)));
ll up[N][lg][K][K];
void umin(ll &a,ll b){
    a=min(a,b);
}
signed main()
{
    fast_io;
    int k,n,m,q;
    cin>>k>>n>>m>>q;
    for(int i=0;i<N;i++){
        for(int j=0;j<lg;j++){
            for(int t=0;t<K;t++){
                for(int p=0;p<K;p++)
                    up[i][j][t][p]=inf;
            }
        }
    }
    for(int i=0;i<m;i++){
        int a,b,t;
        cin>>a>>b>>t;
        umin(up[a/k][0][a%k][b%k],t);
    }
    for(int j=1;j<lg;j++){
        for(int i=0;i<N;i++){
            for(int t=0;t<k;t++){
                if((i+(1<<j))>N)break;
                vec<ll>dst(k,inf);
                for(int pt=0;pt<k;pt++){
                    for(int nt=0;nt<k;nt++){
                        umin(dst[nt],up[i][j-1][t][pt]+up[(i+(1<<(j-1)))][j-1][pt][nt]);
                    }
                }
                for(int pt=0;pt<k;pt++)
                    up[i][j][t][pt]=dst[pt];
            }
        }
    }
    while(q--){
        int a,b;
        cin>>a>>b;
        vec<ll>dst(k,inf);
        dst[a%k]=0;
        int na=a/k,nb=b/k;
        for(int j=lg-1;j>=0;j--){
            if((na+(1<<j))>nb)continue;
//            debug()<<imie(dst);
            vec<ll>nd(k,inf);
            for(int t=0;t<k;t++){
                for(int nt=0;nt<k;nt++){
                    umin(nd[nt],dst[t]+up[na][j][t][nt]);
                }
            }
            dst=nd;
            na+=(1<<j);
//            debug()<<imie(dst);
        }
        cout<<(dst[b%k]==inf?-1:dst[b%k])<<"\n";
    }
    return 0;
}
/*
5 14 5 1
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12

*/

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