oj.uz

Submission #991145

# Submission time Handle Problem Language Result Execution time Memory
991145 2024-06-01T12:19:28 Z JuliaTatad Restore Array (RMI19_restore) C++17
13 / 100
 160 ms 1040 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(0, i, -1));
	}
	//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.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.to] > d[e.from] + e.w) {
				d[e.to] = d[e.from] + e.w;
			}
		}
	}

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 836 KB Output is correct
2 Correct 136 ms 860 KB Output is correct
3 Correct 143 ms 1040 KB Output is correct
4 Correct 136 ms 856 KB Output is correct
5 Correct 157 ms 856 KB Output is correct
6 Correct 158 ms 796 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 836 KB Output is correct
2 Correct 136 ms 860 KB Output is correct
3 Correct 143 ms 1040 KB Output is correct
4 Correct 136 ms 856 KB Output is correct
5 Correct 157 ms 856 KB Output is correct
6 Correct 158 ms 796 KB Output is correct
7 Correct 139 ms 856 KB Output is correct
8 Correct 151 ms 856 KB Output is correct
9 Incorrect 160 ms 860 KB Integer -15 violates the range [-1, 1]
10 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -