oj.uz

Submission #435690

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 15800 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -