// ~ be name khoda ~ //
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 5e3 + 10;
const int MAX_M = 1e4 + 10;
vector <tuple<int, int, int>> e;
int n, m, dis[2][MAX_N], ans[MAX_N];
bool check() {
for(int i = n + 1; i <= 2 * n; i++) {
for(int j = 0; j < e.size(); j++) {
auto [v, u, w] = e[i];
if(dis[(i - 1) & 1][u] > dis[(i - 1) & 1][v] + w)
return true;
}
}
return false;
}
int main() {
cin >> n >> m;
memset(dis, 63, sizeof dis);
for(int i = 0; i < m; i++) {
int l, r, k, val;
cin >> l >> r >> k >> val;
l++;
r++;
if(val == 0) {
e.push_back({l - 1, r, r - l + 1 - k});
}
else {
e.push_back({r, l - 1, -r + l - 2 + k});
}
}
e.push_back({0, 1, 0});
for(int i = 0; i < n; i++) {
e.push_back({i, i + 1, 1});
e.push_back({i + 1, i, 0});
}
dis[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < e.size(); j++) {
auto [v, u, w] = e[j];
dis[i & 1][u] = min({dis[i & 1][u], dis[(i - 1) & 1][u], dis[(i - 1) & 1][v] + w});
}
}
if(check()) {
cout << -1 << endl;
return 0;
}
else {
cout << dis[n&1][1] << " ";
for(int i = 2; i <= n; i++) {
if(dis[n & 1][i] == dis[n & 1][i - 1])
cout << 0 << " ";
else if(dis[n & 1][i] > dis[n & 1][i - 1])
cout << 1 << " ";
else
cout << 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... |