oj.uz

Submission #435642

# Submission time Handle Problem Language Result Execution time Memory
435642 2021-06-23T14:00:54 Z penguinhacker Toll (BOI17_toll) C++14
0 / 100
 114 ms 19780 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 smax(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)
					smax(tl[i][j], tl[a[0]][j]+a[1]);
	}
	for (int i=(mid+1)*k; i<(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)
					smax(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)
					smax(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 47 ms 16836 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9168 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 3 ms 2760 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2680 KB Output is correct
7 Correct 7 ms 3072 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 36 ms 8444 KB Output is correct
10 Runtime error 114 ms 19780 KB Execution killed with signal 11
11 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 Correct 3 ms 2636 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Incorrect 4 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 3 ms 2636 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 3 ms 2680 KB Output is correct
6 Incorrect 4 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 47 ms 16836 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -