oj.uz

Submission #435644

# Submission time Handle Problem Language Result Execution time Memory
435644 2021-06-23T14:06:48 Z penguinhacker Toll (BOI17_toll) C++14
10 / 100
 136 ms 15944 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;
	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];
		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]);
		}
	}
	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 45 ms 15944 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 95 ms 7560 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 2 ms 2636 KB Output is correct
7 Correct 6 ms 3020 KB Output is correct
8 Correct 6 ms 3020 KB Output is correct
9 Correct 39 ms 7512 KB Output is correct
10 Correct 136 ms 9408 KB Output is correct
11 Correct 83 ms 9332 KB Output is correct
12 Correct 51 ms 8580 KB Output is correct
13 Correct 115 ms 11328 KB Output is correct
14 Correct 72 ms 8316 KB Output is correct
15 Correct 58 ms 7464 KB Output is correct
16 Correct 57 ms 7468 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 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 Incorrect 3 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 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 Incorrect 3 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 45 ms 15944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -