Submission #493861

#	Time	Username	Problem	Language	Result	Execution time	Memory
493861		Alexandruabcde	Restore Array (RMI19_restore)	C++14	100 / 100	116 ms	972 KiB

restore

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1000000000;
constexpr int NMAX = 5005;
typedef pair <int, int> PII;

int N, M;
vector <PII> G[NMAX];

int sp[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i ) {
        int L, R, K, Val;

        cin >> L >> R >> K >> Val;

        ++ L;
        ++ R;
        int Lg = R - L + 1;

        if (Val == 0) {
            G[L-1].push_back({Lg-K, R});
        }
        else G[R].push_back({-Lg+K-1, L-1});
    }

    for (int i = 0; i <= N; ++ i )
        sp[i] = INF;

    for (int i = 1; i <= N; ++ i ) {
        int L = i, R = i;
        G[R].push_back({0, L-1});
        G[L-1].push_back({1, R});
    }
}

bool InQueue[NMAX];
int length[NMAX];
bool sol;

void BFS () {
    queue <int> Q;

    Q.push(0);
    InQueue[0] = 1;
    sp[0] = 0;
    length[0] = 1;

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        InQueue[nod] = 0;

        for (auto it : G[nod]) {
            int to = it.second;
            int cost = it.first;

            if (sp[nod] + cost < sp[to]) {
                sp[to] = sp[nod] + cost;
                length[to] = length[nod] + 1;

                if (length[to] > N || sp[to] < 0) {
                    cout << -1 << '\n';
                    return;
                }

                if (!InQueue[to]) {
                    Q.push(to);
                    InQueue[to] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= N; ++ i )
        cout << sp[i] - sp[i-1] << " ";
}

int main () {
    Read();
    BFS();
}

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