Submission #198084

#	Time	Username	Problem	Language	Result	Execution time	Memory
198084		model_code	Restore Array (RMI19_restore)	C++17	100 / 100	123 ms	1016 KiB

restore

/**
* user:  tudose-aad
* fname: Maria Alexa
* lname: Tudose
* task:  restore
* score: 100.0
* date:  2019-10-10 06:37:16.189929
*/
#include <bits/stdc++.h>
#define impossible { cout << "-1\n"; exit(0); }

using namespace std;

const int Nmax = 10005;
typedef long long ll;
const int inf = 5005;


vector<pair<int,int>> v[Nmax];
int n, m;
int dist[Nmax];
bool inQ[Nmax];
int bagat[Nmax];


void add_edge(int x, int y, int c)
{
    v[x].push_back({y, c});
}

void add_res(int i, int j, int k, int val)
{
    if(val == 0)
        add_edge(j, i-1, -k);
    else add_edge(i-1, j, k-1);
}

static bool min_to(int &x, int y)
{
    if(x <= y) return 0;
    x = y;
    if(x < 0) impossible;
    return 1;
}

void bellman(int start)
{
    queue<int> q;
    int i;
    for(i=0; i<=n; ++i) inQ[i] = 0, dist[i] = inf;

    inQ[start] = 1;
    q.push(start);
    dist[start] = 0;

    while(q.size())
    {
        int node = q.front();
        q.pop();
        inQ[node] = 0;

        for(auto it : v[node])
            if(min_to(dist[it.first], dist[node] + it.second))
            {
                ++bagat[it.first];
                if(bagat[it.first] > m) impossible;

                if(!inQ[it.first])
                {
                    inQ[it.first] = 1;
                    q.push(it.first);

                }
            }
    }
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    int i;
    for(i=1; i<=m; ++i)
    {
        int L, R, K, Val;
        cin >> L >> R >> K >> Val;
        ++L; ++R;
        add_res(L, R, K, Val);
    }

    for(i=1; i<=n; ++i)
    {
        add_edge(i-1, i, 1);
        add_edge(i, i-1, 0);
    }

    bellman(0);
    for(i=1; i<=n; ++i) cout << ((dist[i] - dist[i-1]) ^ 1) << ' ';


    return 0;
}

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