Submission #1207851

#TimeUsernameProblemLanguageResultExecution timeMemory
1207851andrejikusRestore Array (RMI19_restore)C++20
100 / 100
269 ms848 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; void DBG() { cerr << "]" << endl; } template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); } #define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) const int N = 5003; ll dist[N]; vector<tuple<int, int, int>> edges; int n, m; void add_edge(int l, int r, int k, int v) { if (v == 0) { int t = (r-l+1)-k; edges.push_back({l-1, r, t}); } else { int t = (r-l+1)-(k-1); edges.push_back({r, l-1, -t}); } } bool bellman_ford() { for (int i = 1; i <= n+1; i++) { for (auto [l, r, t] : edges) { if (dist[r] > dist[l]+t) { dist[r] = dist[l]+t; } } } for (auto [l, r, t] : edges) { if (dist[r] > dist[l]+t) return false; } return true; } void solve() { cin >> n >> m; for(int i=1;i<=n;i++){ dist[i] = 1e18; } for(int i=0;i<n;i++){ edges.push_back({i, i+1, 1}); } for(int i=1;i<=n;i++){ edges.push_back({i, i - 1, 0}); } for(int i=1;i<=m;i++){ int l, r, k, val; cin >> l >> r >> k >> val; ++l; ++r; add_edge(l, r, k, val); } bool ok = bellman_ford(); if (!ok) { cout << -1 << "\n"; return; } for (int i = 1; i <= n; i++) cout << dist[i]-dist[i-1] << " "; cout << "\n"; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...