oj.uz

Submission #367436

# Submission time Handle Problem Language Result Execution time Memory
367436 2021-02-17T10:39:56 Z alextodoran Restore Array (RMI19_restore) C++17
7 / 100
 600 ms 40600 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

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];

void addMinDiff (int u, int v, int d)
{
    edges[u].push_back(Edge{v, -d});
}

void addMaxDiff (int u, int v, int d)
{
    edges[v].push_back(Edge{u, d});
}

int dist[N_MAX];

queue <int> q;

int times[N_MAX];

bool BellmanFord ()
{
    for(int i = 0; i <= n; i++)
        dist[i] = INT_MAX;
    dist[0] = 0;
    q.push(0);
    while(q.empty() == false)
    {
        int u = q.front();
        q.pop();
        if(++times[u] == n + 1)
            return false;
        for(Edge e : edges[u])
            if(dist[u] + e.len < dist[e.u])
            {
                dist[e.u] = dist[u] + e.len;
                q.push(e.u);
            }
    }
    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++)
    {
        addMinDiff(i, i - 1, 0);
        addMaxDiff(i, i - 1, 1);
    }
    for(int i = 1; i <= m; i++)
    {
        int l, r, k;
        bool val;
        cin >> l >> r >> k >> val;
        l++;
        r++;
        if(val == 0)
            addMinDiff(r, l - 1, k);
        else
            addMaxDiff(r, l - 1, 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;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 5 ms 876 KB Output is correct
5 Execution timed out 829 ms 40600 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 876 KB Output is correct
2 Correct 5 ms 876 KB Output is correct
3 Correct 5 ms 876 KB Output is correct
4 Correct 5 ms 876 KB Output is correct
5 Execution timed out 829 ms 40600 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 5 ms 876 KB Output is correct
12 Correct 5 ms 876 KB Output is correct
13 Correct 5 ms 876 KB Output is correct
14 Correct 5 ms 876 KB Output is correct
15 Execution timed out 829 ms 40600 KB Time limit exceeded
16 Halted 0 ms 0 KB -