Submission #164078

#	Time	Username	Problem	Language	Result	Execution time	Memory
164078		nvmdava	Toll (BOI17_toll)	C++17	100 / 100	368 ms	63056 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 50005
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define LEN 240

int fl[250][240][240];
vector<pair<pair<int, int>, int> > tr[250], buck[250];

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

    int k, n, m, o;
    cin>>k>>n>>m>>o;
    memset(fl, 0x3f, sizeof fl);

    for(int i = 0; i < 210; ++i)
    	for(int j = 0; j < 240; ++j)
    		fl[i][j][j] = 0;
    
    while(m--){
    	int a, b, t;
    	cin>>a>>b>>t;
    	if(a / LEN != b / LEN){
    		tr[a / LEN].push_back({{a % k, b % k}, t});
    	} else {
    		buck[a / LEN].push_back({{a % LEN, b % LEN}, t});
    	}
    }
    for(int i = 0; i < 210; ++i){
    	sort(buck[i].begin(), buck[i].end(), [](const pair<pair<int, int>, int>& lhs, const pair<pair<int, int>, int>& rhs){
    		return lhs.ff.ss < rhs.ff.ss;
    	});
    	for(auto& x : buck[i]){
    		for(int j = 0; j <= x.ff.ff; ++j){
    			fl[i][j][x.ff.ss] = min(fl[i][j][x.ff.ss], fl[i][j][x.ff.ff] + x.ss);
    		}
    	}
    }
    while(o--){
    	int a, b;
    	cin>>a>>b;
    	int ans = INF;
    	if(a / LEN == b / LEN){
    		ans = fl[a / LEN][a % LEN][b % LEN];
    	} else {
    		vector<int> tmp(k);
    		for(int i = 0; i < k; ++i){
    			tmp[i] = fl[a / LEN][a % LEN][LEN - k + i];
    		}
    		vector<int> tmp3(k, INF);
    		for(auto& x : tr[a / LEN])
    			tmp3[x.ff.ss] = min(tmp3[x.ff.ss], tmp[x.ff.ff] + x.ss);
    		swap(tmp, tmp3);
    		for(int i = a / LEN + 1; i < b / LEN; ++i){
    			vector<int> tmp2(k, INF);
    			for(int j = 0; j < k; ++j){
    				for(int l = 0; l < k; ++l){
    					tmp2[l] = min(tmp2[l], tmp[j] + fl[i][j][LEN - k + l]);
    				}
    			}
    			swap(tmp, tmp2);

	    		vector<int> tmp4(k, INF);
	    		for(auto& x : tr[i])
	    			tmp4[x.ff.ss] = min(tmp4[x.ff.ss], tmp[x.ff.ff] + x.ss);
	    		swap(tmp, tmp4);
    		}
    		for(int i = 0; i < k; i++){
    			ans = min(ans, tmp[i] + fl[b / LEN][i][b % LEN]);
    		}
    	}
    	cout<<(ans == INF ? -1 : ans)<<'\n';
    }
}

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