Submission #630894

#	Time	Username	Problem	Language	Result	Execution time	Memory
630894		minhcool	Toll (BOI17_toll)	C++17	100 / 100	463 ms	226768 KiB

toll

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 5e4 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int k, n, m, q;
vector<ii> Adj[N];

int dist[N][555];

int mn_dist[N];

void process(){
	cin >> k >> n >> m >> q;
	for(int i = 1; i <= m; i++){
	    int u, v, w;
	    cin >> u >> v >> w;
	    Adj[v].pb({u, w});
	}
	for(int i = 0; i < n; i++){
	    for(int j = i + 1; j <= min(n - 1, i + 550); j++){
	        dist[i][j - i] = oo;
	        for(auto it : Adj[j]){
	            if(it.fi < i) continue;
	            dist[i][j - i] = min(dist[i][j - i], dist[i][it.fi - i] + it.se);
	        }
	    }
	}
	while(q--){
	    int u, v;
	    cin >> u >> v;
	    int temp1 = u / k, temp2 = v / k;
	    if(temp1 >= temp2){
	        cout << "-1\n";
	        continue;
	    }
	    for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[i] = oo;
	    mn_dist[u] = 0;
	    for(; temp1 < (temp2 - 100); temp1 += 100){
	        for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++) mn_dist[i] = oo;
	        for(int i = (temp1 + 100) * k; i < (temp1 + 101) * k; i++){
	            for(int j = temp1 * k; j < (temp1 + 1) * k; j++) mn_dist[i] = min(mn_dist[i], mn_dist[j] + dist[j][i - j]);
	        }
	    }
	    //cout << temp1 << " " << u << " " << v << "\n";
	    //continue;
	    mn_dist[v] = oo;
	    for(int i = temp1 * k; i < (temp1 + 1) * k; i++) mn_dist[v] = min(mn_dist[v], mn_dist[i] + dist[i][v - i]);
	    cout << (mn_dist[v] == oo ? -1 : mn_dist[v]) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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