Submission #991178

#	Time	Username	Problem	Language	Result	Execution time	Memory
991178		JuliaTatad	Restore Array (RMI19_restore)	C++17	0 / 100	1030 ms	141900 KiB

restore

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
const int INF = 1e9; int n; int m;
//vector<vector<int>> gr; vector<bool> used;

struct Edge {
	int from; int to; int w;
	Edge(int from, int to, int w) : from(from), to(to), w(w) {}
};

int main() {
	cin >> n >> m; 
	// we will have n+1 vertices
	vector<Edge> edges;
	
	for (int i = 0; i < m; i++) {
		int l; int r; int k; int v; cin >> l >> r >> k >> v; r++; l++;
		if (v == 0) {
			edges.push_back(Edge(l - 1, r, r + 1 - l - k)); 
		}
		else {
			edges.push_back(Edge(r, l - 1, l + k - r - 2)); 
		}
	}

	for (int i = 1; i <= n; i++){
		edges.push_back(Edge(i-1, i, 1)); edges.push_back(Edge(i, i-1, 0));
	}
	//edges.push_back(Edge(0, 1, 0));

	vector<int> d(n + 1, INF); d[0] = 0;

	for (int i = 0; i < n; i++) {
		for (auto& e : edges) {
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.w) {
				d[e.to] = d[e.from] + e.w;
			}
		}
	}

	vector<int> old = d;

	for (int i = 0; i < n; i++) {
		for (auto& e : edges) {
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.w) {
				d[e.to] = d[e.from] + e.w;
				cout << "updated " << e.to << "\n";
			}
		}
	}

	for (int i = 0; i < n + 1; i++) {
		if (d[i] != old[i]) {
			cout << "-1" << "\n"; return 0;
		}
	}
	// ok so no negative cycles
	vector<int> ans(n);
	for (int i = 1; i <= n; i++) {
		ans[i - 1] = d[i] - d[i - 1]; //std::cout << "i ans = " << i << " " << ans[i-1] << "\n";
		if (ans[i - 1] > 1 or ans[i - 1] < 0) {
			cout << "-1" << "\n"; return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " "; 
	}
	cout << "\n";
}

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