oj.uz

Submission #702476

# Submission time Handle Problem Language Result Execution time Memory
702476 2023-02-24T07:41:00 Z RandomLB Toll (BOI17_toll) C++17
7 / 100
 739 ms 524288 KB 
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
#define F first
#define S second
#define pb push_back
#define siz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ms(x, a) memset(x, a, sizeof(x))
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
	string delim = "";
	cout << vars << " = ";
	(...,(cout << delim << values, delim = ", "));
	cout << endl;
}
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
//=================================
const int MAX = 5e4+5;
vector<pi> adj[MAX], radj[MAX];
int tl[MAX], tr[MAX], res[MAX], dis[5][MAX], k;
bool vis[MAX];

void solve(int l, int r, vector<int> vec){
	if (l/k == r/k) return;
	int m = l+(r-l)/2/k;
	//deb(l, r, m);
	for (int i = 0; i < k; i++){
		for (int j = l; j <= r; j++){
			dis[i][j] = INF;
			vis[j] = false;
		}
		queue<int> q;
		q.push(m*k+i); dis[i][m*k+i] = 0;
		while (siz(q)){
			int v = q.front(); q.pop();
			for (auto[u, w]: radj[v]){
				if (u < l) continue;
				dis[i][u] = min(dis[i][u], dis[i][v]+w);
				if (!vis[u]){ vis[u] = true; q.push(u); }
			}
		}
		q.push((m+1)*k+i); dis[i][(m+1)*k+i] = 0;
		while (siz(q)){
			int v = q.front(); q.pop();
			for (auto[u, w]: adj[v]){
				if (u > r) continue;
				dis[i][u] = min(dis[i][u], dis[i][v]+w);
				if (!vis[u]){ vis[u] = true; q.push(u); }
			}
		}
	}
	//deb(dis[2][0], dis[2][12]);
	vector<int> v1, v2;
	for (int i: vec){
		//deb(i, tl[i], tr[i]);
		if (tl[i]/k <= m && tr[i]/k > m){
			for (int a = 0; a < k; a++){
				for (auto[b, w]: adj[m*k+a]){
					res[i] = min(res[i], dis[a][tl[i]]+w+dis[b-(m+1)*k][tr[i]]);
				}
			}
		} else if (tr[i]/k <= m) v1.pb(i); else v2.pb(i);
	}
	solve(l, (m+1)*k-1, v1); solve((m+1)*k, r, v2);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q; cin >> k >> n >> m >> q;
	for (int i = 1; i <= m; i++){
		int a, b, w; cin >> a >> b >> w;
		adj[a].pb({b, w});
		radj[b].pb({a, w});
	}
	vector<int> v;
	for (int i = 1; i <= q; i++){
		cin >> tl[i] >> tr[i];
		v.pb(i);
	}
	ms(res, INF);
	solve(0, n/k*k+k-1, v);
	for (int i = 1; i <= q; i++) cout << (res[i] < INF? res[i] : -1) << "\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7436 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 2 ms 2948 KB Output is correct
7 Correct 3 ms 2996 KB Output is correct
8 Correct 36 ms 7288 KB Output is correct
9 Correct 32 ms 7116 KB Output is correct
10 Correct 9 ms 3492 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 739 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Runtime error 563 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Runtime error 563 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 7436 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 2 ms 2948 KB Output is correct
7 Correct 3 ms 2996 KB Output is correct
8 Correct 36 ms 7288 KB Output is correct
9 Correct 32 ms 7116 KB Output is correct
10 Correct 9 ms 3492 KB Output is correct
11 Runtime error 739 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -