Submission #1305742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305742		Sofiatpc	Toll (BOI17_toll)	C++20	7 / 100	33 ms	12260 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 5*1e4+5, MAX = 15, INF = 1e9;
vector<int> adj[MAXN], w[MAXN];
int mn[MAX+5][5][MAXN];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int k,n,m,q; cin>>k>>n>>m>>q;
    
    for(int i = 0; i <= MAX; i++)
        for(int md = 0; md < k; md++)
            for(int j = 0; j < n; j++)mn[i][md][j] = INF;

    for(int i = 0; i < m; i++){
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back(b); w[a].push_back(c);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < sz(adj[i]); j++){
            int viz = adj[i][j];
            mn[0][viz%k][i] = min( mn[0][viz%k][i], w[i][j] );
        }
    }

    for(int i = 1; i <= MAX; i++)
        for(int md = 0; md < k; md++)
            for(int j = 0; j < n; j++){
                for(int md2 = 0; md2 < k; md2++){
                    mn[i][md][j] = min( mn[i][md][j], mn[i-1][md2][j] + mn[i-1][md][ j + (1<<(i-1))*k + md2 ] );
                }
            }
    
    while(q--){
        int a,b; cin>>a>>b;

        int qtd = b/k-a/k;

        int cur[5]; for(int md = 0; md < k; md++)cur[md] = INF; cur[a%k] = 0;

        a = (a/k)*k;
        for(int i = MAX; i >= 0; i--)
            if(qtd & (1<<i)){
                int nxt[5]; for(int md = 0; md < k; md++)nxt[md] = INF;

                for(int md = 0; md < k; md++)
                    for(int md2 = 0; md2 < k; md2++){
                        nxt[md] = min(nxt[md], cur[md2] + mn[i][md][ a+ md2] );
                    }
                a += (1<<i)*k;

                for(int md = 0; md < k; md++)cur[md] = nxt[md];
            }

        if(cur[b%k] == INF)cout<<"-1\n";
        else cout<<cur[b%k]<<"\n";
    }
}   

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