Submission #698349

#	Time	Username	Problem	Language	Result	Execution time	Memory
698349		badont	Toll (BOI17_toll)	C++17	100 / 100	277 ms	23920 KiB

toll

#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
ll T;

void solve() {
	ll n, m, k, o;
	cin >> k >> n >> m >> o;

	vector e(n, vector<pii>()), re(n, vector<pii>());
	vector fwd(n, vector<int>(k, 0)), bkwd(n, vector<int>(k, 0));
	while (m--) {
		ll x, y, t;
		cin >> x >> y >> t;
		e[x].pb({y, t});
		fwd[x][y % k] = t;
		re[y].pb({x, y});
		bkwd[y][x % k] = t;
	}

	const ll INF = 1e18;

	vector<pii> queries(o);
	for (auto& [x, y] : queries) {
		cin >> x >> y;
	}

	vector<int> ans(o);
	auto dfs = [&](auto dfs, int l, int r, vector<int>& rel) -> void {
		assert(l <= r);
		debug(l, r);
		if (l == r) {
			for (auto& idx : rel) {
				debug(idx);
				assert(idx < o);
				ans[idx] = -1;
			}
			rel.clear();
			return;
		}
		int m = (l + r) >> 1;

		vector dpl(m - l + 1, vector(k, vector<ll>(k, INF)));
		vector dpr(r - m, vector(k, vector<ll>(k, INF)));
		vector<int> to_left, to_right;

		F0R (i, k) dpl[0][i][i] = dpr[0][i][i] = 0;
		for (int lp = m - 1, idx = 1; lp >= l; lp--, idx++) {
			F0R (x, k) F0R (y, k) F0R (z, k) {
				int start_node = lp * k + x;
				if (start_node < n and fwd[start_node][y] != 0) {
					dpl[idx][x][z] = min(dpl[idx][x][z],
						dpl[idx - 1][y][z] + fwd[start_node][y]
					);
				}
			}
		}

		///debug("here");

		for (int rp = m + 2, idx = 1; rp <= r; rp++, idx++) {
			F0R (x, k) F0R (y, k) F0R (z, k) {
				int start_node = rp * k + x;
				if (start_node < n and bkwd[start_node][y] != 0) {
					dpr[idx][x][z] = min(dpr[idx][x][z],
						dpr[idx - 1][y][z] + bkwd[start_node][y]
					);
				}
			}
		}

		//debug("here");

		for (auto& qid : rel) {
			auto& [l, r] = queries[qid];
			if (r / k <= m) {
				to_left.pb(qid);
			} else if (l / k > m) {
				to_right.pb(qid);
			} else {
				int lpos = l / k, lmod = l % k;
				int rpos = r / k, rmod = r % k;
				ll res = INF;

				int lidx = m - lpos;
				int ridx = rpos - (m + 1);

				//debug(l, r, m, lpos, rpos);
				//debug(lidx, ridx);

				F0R (i, k) F0R (j, k) {
					int start_pos = m * k + i;
					if (start_pos < n and fwd[start_pos][j] != 0) {
						res = min(res, 
							dpl[lidx][lmod][i] + fwd[start_pos][j] + dpr[ridx][rmod][j]);
					}
				}

				ans[qid] = (res >= INF ? -1 : res);
			}
		}


		dpl.clear();
		dpr.clear();
		rel.clear();
		dfs(dfs, l, m, to_left);
		dfs(dfs, m + 1, r, to_right);
	};

	vector<int> init(o);
	iota(all(init), 0);
	dfs(dfs, 0, (n - 1) / k, init);

	for (auto& u : ans)
		cout << u << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message (stderr)

toll.cpp: In instantiation of 'solve()::<lambda(auto:23, int, int, std::vector<int>&)> [with auto:23 = solve()::<lambda(auto:23, int, int, std::vector<int>&)>]':
toll.cpp:148:31:   required from here
toll.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
toll.cpp:66:3: note: in expansion of macro 'debug'
   66 |   debug(l, r);
      |   ^~~~~
toll.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
toll.cpp:69:5: note: in expansion of macro 'debug'
   69 |     debug(idx);
      |     ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44