Submission #1207848

#TimeUsernameProblemLanguageResultExecution timeMemory
1207848andrejikusRestore Array (RMI19_restore)C++20
0 / 100
79 ms836 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 < m; i++) { int l, r, k, v; cin >> l >> r >> k >> v; l++; r++; add_edge(l, r, k, v); } for (int i = 1; i <= n; i++) edges.push_back({i-1, i, 1}); for (int i = 1; i <= n; i++) edges.push_back({i, i-1, 0}); 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...