oj.uz

답안 #472608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
472608 2021-09-13T19:29:45 Z disastah Toll (BOI17_toll) C++17
7 / 100
 122 ms 75460 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=2e9+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) {
	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+1);
	while(q--) {
		int a, b; cin >> a >> b;
		if (a/k==b/k) {
			cout << "-1\n";
			continue;
		}
		int h=__builtin_ctz(dst_mask[a]^dst_mask[b]);
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 39240 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 3 ms 3148 KB Output is correct
8 Correct 58 ms 39224 KB Output is correct
9 Correct 51 ms 39108 KB Output is correct
10 Correct 23 ms 36232 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 122 ms 75384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 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 2 ms 2636 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 5 ms 3244 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 61 ms 39128 KB Output is correct
11 Runtime error 113 ms 75460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 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 2 ms 2636 KB Output is correct
6 Correct 3 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 5 ms 3244 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 61 ms 39128 KB Output is correct
11 Runtime error 113 ms 75460 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 39240 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 3 ms 3148 KB Output is correct
8 Correct 58 ms 39224 KB Output is correct
9 Correct 51 ms 39108 KB Output is correct
10 Correct 23 ms 36232 KB Output is correct
11 Runtime error 122 ms 75384 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -