Submission #367441

#	Time	Username	Problem	Language	Result	Execution time	Memory
367441		alextodoran	Restore Array (RMI19_restore)	C++17	7 / 100	747 ms	1004 KiB

restore

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

typedef long long ll;

const int N_MAX = 5002;
const int M_MAX = 10002;

int n, m;

struct Edge
{
    int u;
    int len;
};

vector <Edge> edges[N_MAX];

int dist[N_MAX];

queue <int> q;

int times[N_MAX];

bool inq[N_MAX];

bool BellmanFord ()
{
    for(int i = 0; i <= n; i++)
        dist[i] = INT_MAX;
    dist[0] = 0;
    inq[0] = true;
    q.push(0);
    while(q.empty() == false)
    {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(Edge &e : edges[u])
            if(dist[u] + e.len < dist[e.u])
            {
                dist[e.u] = dist[u] + e.len;
                if(inq[e.u] == false)
                {
                    q.push(e.u);
                    inq[e.u] = true;
                }
                if(++times[e.u] >= n)
                    return false;
            }
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        edges[i].push_back(Edge{i - 1, 0});
        edges[i - 1].push_back(Edge{i, 1});
    }
    for(int i = 1; i <= m; i++)
    {
        int l, r, k;
        bool val;
        cin >> l >> r >> k >> val;
        l++;
        r++;
        if(val == 0)
            edges[r].push_back(Edge{l - 1, -k});
        else
            edges[l - 1].push_back(Edge{r, k - 1});
    }
    if(BellmanFord() == true)
    {
        for(int i = 1; i <= n; i++)
            cout << 1 - (dist[i] - dist[i - 1]) << " ";
        cout << "\n";
    }
    else
        cout << "-1\n";
    return 0;
}

Compilation message (stderr)

restore.cpp:12: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   12 | #pragma GCC optimization ("O3")
      | 
restore.cpp:13: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   13 | #pragma GCC optimization ("unroll-loops")
      |

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