oj.uz

답안 #991146

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
991146 2024-06-01T12:22:11 Z JuliaTatad Restore Array (RMI19_restore) C++17
13 / 100
 157 ms 720 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
	vector<int> ans(n);
	for (int i = 1; i <= n; i++) {
		ans[i - 1] = d[i] - d[i - 1];
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 604 KB Output is correct
2 Correct 130 ms 604 KB Output is correct
3 Correct 126 ms 600 KB Output is correct
4 Correct 126 ms 720 KB Output is correct
5 Correct 148 ms 604 KB Output is correct
6 Correct 149 ms 624 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 604 KB Output is correct
2 Correct 130 ms 604 KB Output is correct
3 Correct 126 ms 600 KB Output is correct
4 Correct 126 ms 720 KB Output is correct
5 Correct 148 ms 604 KB Output is correct
6 Correct 149 ms 624 KB Output is correct
7 Correct 133 ms 720 KB Output is correct
8 Correct 157 ms 604 KB Output is correct
9 Incorrect 128 ms 604 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -