Submission #1149220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149220		MisterReaper	Restore Array (RMI19_restore)	C++20	0 / 100	55 ms	580 KiB

restore

// File A.cpp created on 11.02.2025 at 21:28:31
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

bool chmin(int& a, int b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;
    std::vector<int> L(M), R(M), K(M), V(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> L[i] >> R[i] >> K[i] >> V[i];
    }

    std::vector<std::array<int, 3>> edges(M + N);
    for (int i = 0; i < M; ++i) {
        if (V[i] == 0) {
            edges[i] = {R[i] + 1, L[i], -K[i]};
        } else {
            edges[i] = {L[i], R[i] + 1, K[i] - 1};
        }
    }
    for (int i = 0; i < N; ++i) {
        edges[M + i] = {i, i + 1, +1};
    }

    constexpr int inf = int(1E9);

    std::vector<int> dis(N + 1, inf);
    dis[0] = 0;
    for (int t = 0; t < N; ++t) {
        bool fnd = false;
        for (int i = 0; i < M + N; ++i) {
            if (chmin(dis[edges[i][1]], dis[edges[i][0]] + edges[i][2])) {
                fnd = true;
            }
        }
        if (t == N - 1 && fnd) {
            std::cout << "-1\n";
            return 0;
        }
    }

    debug(dis);

    for (int i = 0; i < N; ++i) {
        if (dis[i + 1] != dis[i]) {
            std::cout << "0 ";
        } else {
            std::cout << "1 ";
        }
    }
    std::cout << '\n';

    return 0;
}

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