oj.uz

답안 #435690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
435690 2021-06-23T15:04:42 Z penguinhacker Toll (BOI17_toll) C++14
10 / 100
 125 ms 15800 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e4, mxQ=1e4;
int n, m, k, q, ans[mxQ];
ar<int, 2> qry[mxQ];
vector<ar<int, 2>> bef[mxN], aft[mxN];
int tl[mxN][5], tr[mxN][5];

void smin(int& x, int y) {
	if (x==-1||y<x)
		x=y;
}

void solve(int l, int r, vector<int>& v) {
	if (v.empty())
		return;
	assert(l^r);
	int mid=(l+r)/2;
	for (int i=mid*k; i<(mid+1)*k; ++i) {
		memset(tl[i], -1, sizeof(tl[i]));
		memset(tr[i], -1, sizeof(tr[i]));
		tl[i][i%k]=tr[i][i%k]=0;
	}
	for (int i=mid*k-1; i>=l*mid; --i) {
		memset(tl[i], -1, sizeof(tl[i]));
		for (int j=0; j<k; ++j)
			for (ar<int, 2> a : aft[i])
				if (tl[a[0]][j]^-1)
					smin(tl[i][j], tl[a[0]][j]+a[1]);
	}
	for (int i=(mid+1)*k; i<min(n, (r+1)*k); ++i) {
		memset(tr[i], -1, sizeof(tr[i]));
		for (int j=0; j<k; ++j)
			for (ar<int, 2> a : bef[i])
				if (tr[a[0]][j]^-1)
					smin(tr[i][j], tr[a[0]][j]+a[1]);
	}
	vector<int> vl, vr;
	for (int i : v) {
		int ql=qry[i][0], qr=qry[i][1];
		assert(l*k<=ql&&qr<(r+1)*k);
		if (qr/k<mid)
			vl.push_back(i);
		else if (ql/k>mid)
			vr.push_back(i);
		else {
			ans[i]=-1;
			for (int j=0; j<k; ++j)
				if (tl[ql][j]^-1&&tr[qr][j]^-1)
					smin(ans[i], tl[ql][j]+tr[qr][j]);
		}
	}
	vector<int>().swap(v);
	solve(l, mid-1, vl);
	solve(mid+1, r, vr);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n >> m >> q;
	for (int i=0; i<m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		aft[u].push_back({v, w});
		bef[v].push_back({u, w});
	}
	vector<int> inds;
	for (int i=0; i<q; ++i) {
		cin >> qry[i][0] >> qry[i][1];
		if (qry[i][0]/k==qry[i][1]/k)
			ans[i]=-1;
		else
			inds.push_back(i);
	}
	solve(0, (n-1)/k, inds);
	for (int i=0; i<q; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 7408 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 3 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 2636 KB Output is correct
7 Correct 7 ms 3020 KB Output is correct
8 Correct 9 ms 2996 KB Output is correct
9 Correct 45 ms 7484 KB Output is correct
10 Correct 125 ms 9284 KB Output is correct
11 Correct 69 ms 9156 KB Output is correct
12 Correct 54 ms 8512 KB Output is correct
13 Correct 96 ms 11384 KB Output is correct
14 Correct 81 ms 8356 KB Output is correct
15 Correct 56 ms 7420 KB Output is correct
16 Correct 62 ms 7360 KB Output is correct

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 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 Incorrect 2 ms 2764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 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 Incorrect 2 ms 2764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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