oj.uz

Submission #484844

# Submission time Handle Problem Language Result Execution time Memory
484844 2021-11-05T15:45:58 Z blue Restore Array (RMI19_restore) C++17
0 / 100
 253 ms 844 KB 
#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;
#define pb push_back

const int INF = 1'000'000;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vi u, v, w;

    for(int j = 1; j <= M; j++)
    {
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++;
        r++;

        if(val == 0)
        {
            u.pb(l-1);
            v.pb(r);
            w.pb(r-l+1 - k);
        }
        else
        {
            u.pb(r);
            v.pb(l-1);
            w.pb(-(r-l+2 - k));
        }
    }

    for(int i = 0; i < N; i++)
    {
        u.pb(i);
        v.pb(i+1);
        w.pb(1);

        u.pb(i+1);
        v.pb(i);
        w.pb(0);
    }

    vi sp(1+N, INF);
    sp[0] = 0;

    for(int q = 1; q <= N; q++)
    {
        for(int j = 0; j < N+M; j++)
        {
            sp[v[j]] = min(sp[v[j]], sp[u[j]] + w[j]);
        }
    }

    bool works = 1;
    for(int j = 0; j < N+M; j++)
        if(sp[v[j]] > sp[u[j]] + w[j])
            works = 0;

    if(!works) cout << "-1\n";
    else
    {
        for(int i = 1; i <= N; i++)
        {
            cout << (sp[i] != sp[i-1]) << ' ';
        }
        cout << '\n';
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 253 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -