Submission #1106850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106850		VectorLi	Restore Array (RMI19_restore)	C++17	100 / 100	238 ms	1272 KiB

restore

#include <bits/stdc++.h>
#define long long long

using namespace std;

const int N = 5000;

int n, m;
vector<pair<int, int>> e[N + 1];

int d[N + 1];

void BF(int x) {
	fill(d, d + n + 1, numeric_limits<int>::max());
	d[x] = 0;
	for (int i = 0; i < n; i++) {
		for (int u = 0; u < n + 1; u++) {
			for (auto [v, w] : e[u]) {
				if (d[u] < numeric_limits<int>::max()) {
					d[v] = min(d[v], d[u] + w);
				}
			}
		}
	}
	for (int u = 0; u < n + 1; u++) {
		for (auto [v, w] : e[u]) {
			if (d[v] > d[u] + w) {
				cout << 0 - 1 << "\n";
				exit(0);
			}
		}
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i <= n - 1; i++) {
		e[i + 1].push_back({i, 0});
		e[i].push_back({i + 1, 1});
	}
	for (int i = 0; i < m; i++) {
		int l, r;
		int k, x;
		cin >> l >> r >> k >> x;
		l = l + 1;
		r = r + 1;
		if (x == 0) {
			e[r].push_back({l - 1, 0 - k});
		} else {
			e[l - 1].push_back({r, k - 1});
		}
	}
	BF(0);
	for (int i = 1; i <= n; i++) {
		if (d[i] - d[i - 1] == 0) {
			cout << 1 << " ";
		} else {
			cout << 0 << " ";
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55