Submission #1212260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212260		3lektra	Toll (BOI17_toll)	C++20	0 / 100	117 ms	170800 KiB

toll

#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5;
const int lg = 17;
const int inf_set = 0x3f;
const int inf_comp = 0x3f3f3f3f;
int k;
vector<pair<int,int>> graph[maxN];
//pair<int,int> par[maxN][lg];
int dp[maxN][5][lg][5];
bool vis[maxN];

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

    int t, n, m, a, b, c, d;
    cin >> k >> n >> m >> t;
    queue<int> tv;

    //memset(graph, 0, sizeof(graph));
    //memset(par, -1, sizeof(par));
    memset(dp, inf_set, sizeof(dp));
    memset(vis, 0, sizeof(vis));
    
    // EDGES
    for(int i = 0; i < m; ++i){
        cin >> a >> b >> d;
        graph[a].push_back({b,d});
        dp[a/k][a%k][0][b%k] = d;
    }

    // EXPLORING THE GRAPH
    for(int deepness = 0; deepness < (n+k-1)/k; ++deepness){
        for(int mod = 0; mod < k; ++mod){
            for(int i = 1; i < lg; ++i){ // Layers to go up
                for(int j = 0; j < k; ++j){ // Mod of the layer you go up to
                    for(int h = 0; h < k; ++h){ // Mod of the layer you transverse
                        if(deepness + (1<<(i-1)) < (n+k-1)/k) dp[deepness][mod][i][j] = min(dp[deepness][mod][i][j], dp[deepness][mod][i-1][h] + dp[deepness + (1<<(i-1))][h][i-1][j]); 
                        //cout << deepness << ' ' << mod << ' ' << i << ' ' << j << ' ' << h << '\n';   
                    }
                }
            }
        }
    }
    
    // QUERIES
    int queries[k][k]; // New layer, Mod
    int temp[k][k];

    while(t--){
        cin >> a >> b;
        if((b/k) <= (a/k)) cout << -1 << '\n';
        else{
            memset(queries, inf_set, sizeof(queries));
            for(int i = 0; i < k; ++i) queries[i][i] = 0;
            
            c = a/k;
            d = (b/k) - (a/k); // distance from one to another
            for(int i = lg-1; i >= 0; --i){
                if(d&(1<<i)){
                    //cout << i << '\n';
                    memset(temp, inf_set, sizeof(temp));
                    for(int ori = 0; ori < k; ++ori){
                        for(int dest = 0; dest < k; ++dest){
                            for(int mid = 0; mid < k; ++mid){
                                temp[ori][dest] = min(temp[ori][dest], queries[ori][mid] + dp[c][mid][i][dest]);
                            }
                        }
                    }
                    memcpy(queries, temp, sizeof(temp));
                    c += (1<<i);
                    //if(c >= d) break;
                }
            }

            if(queries[a%k][b%k] != inf_comp) cout << queries[a%k][b%k] << '\n';
            else cout << -1 << '\n';
        }
   }
   return 0;
}

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