제출 #1237696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237696		dbence	Restore Array (RMI19_restore)	C++20	100 / 100	119 ms	700 KiB

restore

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (x).size()
#define lsb(x) (x) & (-x)
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template <typename T>
void print(T t) {
    cout << t << "\n";
}

template <typename T, typename... Args>
void print(T t, Args ...args) {
    cout << t << " ";
    print(args...);
}

const int N = 5005;
const int M = 20005;
const int inf = 1 << 29;
int n, m, a[N], d[N];

struct Edge {
    int u, v, w;
};
Edge edge[M];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int l, r, k, value;
        cin >> l >> r >> k >> value; l++, r++;
        if (value == 1) {
            edge[i] = {l - 1, r, k - 1};
        } else {
            edge[i] = {r, l - 1, -k};
        }
    }
    for (int i = 0; i < n; ++i) {
        edge[m++] = {i, i + 1, 1};
        edge[m++] = {i + 1, i, 0};
    }
    fill(d + 1, d + n + 1, inf);
    for (int _ = 0; _ < n; ++_) {
        bool changed = false;
        for (int i = 0; i < m; ++i) {
            auto [u, v, w] = edge[i];
            changed |= d[v] > d[u] + w;
            d[v] = min(d[v], d[u] + w);
        }
        if (_ == n - 1 && changed) {
            cout << "-1\n";
            return 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = d[i] - d[i - 1];
    }
    for (int i = 1; i <= n; ++i) {
        cout << !a[i] << " ";
    }
    cout << "\n";
}

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