oj.uz

Submission #991178

# Submission time Handle Problem Language Result Execution time Memory
991178 2024-06-01T13:55:59 Z JuliaTatad Restore Array (RMI19_restore) C++17
0 / 100
 600 ms 141900 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Expected integer, but "updated" found
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1052 KB Output is correct
2 Correct 197 ms 1048 KB Output is correct
3 Correct 183 ms 1048 KB Output is correct
4 Correct 203 ms 1052 KB Output is correct
5 Execution timed out 1030 ms 141900 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 1052 KB Output is correct
2 Correct 197 ms 1048 KB Output is correct
3 Correct 183 ms 1048 KB Output is correct
4 Correct 203 ms 1052 KB Output is correct
5 Execution timed out 1030 ms 141900 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Expected integer, but "updated" found
6 Halted 0 ms 0 KB -