Submission #1105865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105865		koukirocks	Toll (BOI17_toll)	C++17	100 / 100	99 ms	38484 KiB

toll

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int main() {
    speed;
    int n,m,k,q;
    cin>>k>>n>>m>>q;
    vvector<ll> G(n,vector<ll>(k,oo));
    for (int i=0;i<m;i++) {
        ll a,b,w;
        cin>>a>>b>>w;
        G[a][b%k]=min(G[a][b%k],w);
    }
    ll spt[n/k+10][k][k][20];
    for (int i=n-1;i>=0;i--) {
        int ik=i/k;
        int ir=i%k;
        for (int j=0;j<k;j++) spt[ik][ir][j][0]=G[i][j];
        for (int l=1;l<20;l++) {
            for (int j=0;j<k;j++) {
                spt[ik][ir][j][l]=oo;
                if (ik+(1<<l)<=(n-1)/k) {
                    for (int mid=0;mid<k;mid++) {
                        spt[ik][ir][j][l]=min(spt[ik][ir][j][l],spt[ik][ir][mid][l-1]+spt[ik+(1<<(l-1))][mid][j][l-1]);
                        // cout<<mid<<" "<<spt[ik][ir][mid][l-1]<<" "<<spt[ik+(1<<(l-1))][mid][j][l-1]<<" mid spt\n";
                    }
                    // cout<<ik<<" "<<ir<<" "<<j<<" "<<l<<" "<<spt[ik][ir][j][l]<<" ik ir j l spt\n";
                }
            }
        }
    }
    while (q--) {
        int a,b;
        cin>>a>>b;
        int ia=a/k;
        int ra=a%k;
        int ib=b/k;
        int rb=b%k;
        int x=ia;
        ll md[k];
        for (int i=0;i<k;i++) md[i]=oo;
        md[ra]=0;
        for (int l=19;l>=0;l--) {
            // cout<<l<<" l\n";
            if (ib-x>=(1<<l)) {
                ll nmd[k];
                memset(nmd,0x3f,sizeof(nmd));
                for (int i=0;i<k;i++) {
                    for (int j=0;j<k;j++) {
                        nmd[j]=min(nmd[j],md[i]+spt[x][i][j][l]);
                    }
                }
                x+=(1<<l);
                for (int i=0;i< k;i++) md[i]=nmd[i];
                // cout<<x<<" x\n";
                // for (int i=0;i<k;i++) cout<<md[i]<<" ";
                // cout<<"\n";
            }
        }
        cout<<(md[rb]>=oo?-1:md[rb])<<"\n";
    }
    return 0;
}


/*
3 10 9 1
0 3 1
3 6 2
6 9 3
0 4 2
4 7 1
7 9 4
0 5 4
5 8 3
8 9 2
3 9
*/

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