oj.uz

Submission #472596

# Submission time Handle Problem Language Result Execution time Memory
472596 2021-09-13T19:11:11 Z disastah Toll (BOI17_toll) C++17
7 / 100
 92 ms 39296 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+9;
const ll linf=4e18+18;
const int N=5e4;

int k, n, m, q;
vector<ar<int,2>> g[N], rg[N];
ll dst[20][N][5]; int dst_mask[N];

void build_dst(int h, int l, int r) {
	assert(l<r);
	int m=(l+r)/2;
	for (int i=m*k; i<r*k; ++i) dst_mask[i]^=(1<<h);
	for (int k0=0; k0<k; ++k0) {
		dst[h][m*k+k0][k0]=0;
		for (int i=m*k+k0-1; i>=l*k; --i) {
			dst[h][i][k0]=inf;
			for (auto &[u,t] : g[i]) {
				if (u>m*k+k0) continue;
				dst[h][i][k0]=min(dst[h][i][k0],dst[h][u][k0]+t);
			}
		}
		for (int i=m*k+k0+1; i<r*k; ++i) {
			dst[h][i][k0]=inf;
			for (auto &[u,t] : rg[i]) {
				if (u<m*k+k0) continue;
				dst[h][i][k0]=min(dst[h][i][k0],dst[h][u][k0]+t);
			}
		}
	}
	if (l+1<r) {
		build_dst(h+1,l,m);
		build_dst(h+1,m,r);
	}
}

void solve() {
	cin >> k >> n >> m >> q;
	for (int i=0; i<m; ++i) {
		int a, b, t; cin >> a >> b >> t;
		g[a].push_back({b,t});
		rg[b].push_back({a,t});
	}
	build_dst(0,0,(n+k-1)/k);
	while(q--) {
		int a, b; cin >> a >> b;
		int h=__builtin_ctz(dst_mask[a]^dst_mask[b]);
		assert(h<30);
		ll ans=inf;
		for (int i=0; i<k; ++i) ans=min(ans,dst[h][a][i]+dst[h][b][i]);
		cout << (ans<inf?ans:-1) << "\n";
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
#ifdef disastah
	cout << "Output\n\n";
#endif
	int tt=1;
//	cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 39296 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 56 ms 39260 KB Output is correct
9 Correct 55 ms 39108 KB Output is correct
10 Correct 23 ms 36080 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 37324 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Runtime error 7 ms 5196 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Runtime error 8 ms 5196 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Runtime error 8 ms 5196 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 39296 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 56 ms 39260 KB Output is correct
9 Correct 55 ms 39108 KB Output is correct
10 Correct 23 ms 36080 KB Output is correct
11 Correct 92 ms 37324 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Runtime error 7 ms 5196 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -