제출 #1149223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149223		MisterReaper	Restore Array (RMI19_restore)	C++20	100 / 100	427 ms	856 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 + 2 * 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};
    }
    for (int i = 0; i < N; ++i) {
        edges[M + N + i] = {i + 1, i, 0};
    }

    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 + 2 * 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: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55