This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int infinity = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
// vector<vii> graph(n + 2);
vector<pair<pii, int>> edges;
for (int i = 0; i < m; i++) {
int l, r, k, val;
cin >> l >> r >> k >> val;
r++;
int sz = r - l;
if (val) {
edges.push_back({{r, l}, k - sz - 1});
// graph[r].push_back({l, k - n});
} else {
edges.push_back({{l, r}, sz - k});
// graph[l].push_back({r, n - k});
}
}
for (int i = 0; i <= n; i++) {
edges.push_back({{n + 1, i}, 0});
// graph[n + 1].push_back({i, 0});
}
for (int i = 0; i < n; i++) {
edges.push_back({{i, i + 1}, 1});
edges.push_back({{i + 1, i}, 0});
}
vi distances(n + 2, infinity);
distances[n + 1] = 0;
for (int t = 0; t <= n + 2; t++) {
for (auto [p, w] : edges) {
auto [a, b] = p;
chkmin(distances[b], distances[a] + w);
}
}
for (auto [p, w] : edges) {
auto [a, b] = p;
if (distances[b] > distances[a] + w) {
cout << -1 << '\n';
return 0;
}
}
int x = distances[0];
// vi v(n + 1);
// for (int i = 1; i <= n; i++) {
// v[i] = v[i - 1] + distances[i] - x;
// }
for (int i = 1; i <= n; i++) {
cout << distances[i] - distances[i - 1] << ' ';
}
return 0;
}
Compilation message (stderr)
restore.cpp: In function 'int main()':
restore.cpp:2:11: warning: unused variable 'first' [-Wunused-variable]
2 | #define x first
| ^~~~~
restore.cpp:59:9: note: in expansion of macro 'x'
59 | int x = distances[0];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |