Submission #548152

#	Time	Username	Problem	Language	Result	Execution time	Memory
548152		elazarkoren	Restore Array (RMI19_restore)	C++17	100 / 100	459 ms	972 KiB

restore

#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];
      |         ^

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55