Submission #548152

#TimeUsernameProblemLanguageResultExecution timeMemory
548152elazarkorenRestore Array (RMI19_restore)C++17
100 / 100
459 ms972 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...