oj.uz

Submission #493856

# Submission time Handle Problem Language Result Execution time Memory
493856 2021-12-13T08:18:59 Z Alexandruabcde Restore Array (RMI19_restore) C++14
0 / 100
 600 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1000000000;
constexpr int NMAX = 5005;
typedef pair <int, int> PII;

int N, M;
vector <PII> G[NMAX];

int sp[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= M; ++ i ) {
        int L, R, K, Val;

        cin >> L >> R >> K >> Val;

        ++ L;
        ++ R;
        int Lg = R - L + 1;

        if (Val == 0) {
            G[L-1].push_back({Lg-K, R});
        }
        else G[R].push_back({-Lg+K-1, L-1});
    }

    for (int i = 0; i <= N; ++ i )
        sp[i] = INF;

    for (int i = 1; i <= N; ++ i ) {
        int L = i, R = i;
        int K = 1, Lg = 1;
        G[R].push_back({0, L-1});
        G[L-1].push_back({1, R});
    }
}

bool InQueue[NMAX];
int viz[NMAX];
bool sol;

void BFS () {
    queue <int> Q;

    Q.push(0);
    InQueue[0] = 1;
    sp[0] = 0;

    while (!Q.empty()) {
        int nod = Q.front();
        Q.pop();
        InQueue[nod] = 0;

        for (auto it : G[nod]) {
            int to = it.second;
            int cost = it.first;

            if (sp[nod] + cost < sp[to]) {
                sp[to] = sp[nod] + cost;

                if (!InQueue[to]) {
                    Q.push(to);
                    InQueue[to] = 1;
                    viz[to] ++;
                }

                if (viz[to] > N) {
                   // cout << -1 << '\n';
                   // return;
                }
            }
        }
    }

    for (int i = 1; i <= N; ++ i )
        cout << sp[i] - sp[i-1] << " ";
}

int main () {
    Read();
    BFS();
}

Compilation message

restore.cpp: In function 'void Read()':
restore.cpp:40:13: warning: unused variable 'K' [-Wunused-variable]
   40 |         int K = 1, Lg = 1;
      |             ^
restore.cpp:40:20: warning: unused variable 'Lg' [-Wunused-variable]
   40 |         int K = 1, Lg = 1;
      |                    ^~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 1082 ms 332 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 844 KB Output is correct
2 Correct 17 ms 904 KB Output is correct
3 Correct 14 ms 972 KB Output is correct
4 Correct 13 ms 900 KB Output is correct
5 Execution timed out 1089 ms 844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 844 KB Output is correct
2 Correct 17 ms 904 KB Output is correct
3 Correct 14 ms 972 KB Output is correct
4 Correct 13 ms 900 KB Output is correct
5 Execution timed out 1089 ms 844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 1082 ms 332 KB Time limit exceeded
6 Halted 0 ms 0 KB -