oj.uz

답안 #559099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559099 2022-05-09T11:31:16 Z Tenis0206 Restore Array (RMI19_restore) C++11
7 / 100
 600 ms 856 KB 
#include <bits/stdc++.h>

using namespace std;

const int oo = 0x3f3f3f3f;

int n,m;

int d[5005],nr[5005];
bool sel[5005];

vector<pair<int,int>> G[5005];

void Bellman()
{
    queue<int> q;
    for(int i=0; i<=n; i++)
    {
        d[i] = oo;
        sel[i] = false;
    }
    d[0] = 0;
    sel[0] = true;
    q.push(0);
    nr[0] = 1;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        sel[nod] = false;
        for(auto it : G[nod])
        {
            if(d[nod] + it.second < d[it.first])
            {
                d[it.first] = d[nod] + it.second;
                if(!sel[it.first])
                {
                    q.push(it.first);
                    sel[it.first] = true;
                }
                ++nr[it.first];
                if(nr[it.first]>n)
                {
                    cout<<-1<<'\n';
                    return;
                }
            }
        }
    }
    for(int i=0;i<=n;i++)
    {
        for(auto it : G[i])
        {
            if(d[i] + it.second < d[it.first])
            {
                cout<<-1<<'\n';
                return;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<d[i] - d[i-1]<<' ';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        G[i-1].push_back({i,1});
        G[i].push_back({i-1,0});
    }
    for(int i=1; i<=m; i++)
    {
        int l,r,k,val;
        cin>>l>>r>>k>>val;
        ++l;
        ++r;
        if(val==0)
        {
            G[l-1].push_back({r,(r - l + 1) - k});
        }
        else
        {
            G[r].push_back({l-1,-((r - l + 1) - (k - 1))});
        }
    }
    Bellman();
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 852 KB Output is correct
2 Correct 13 ms 856 KB Output is correct
3 Correct 13 ms 852 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Execution timed out 630 ms 852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 852 KB Output is correct
2 Correct 13 ms 856 KB Output is correct
3 Correct 13 ms 852 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Execution timed out 630 ms 852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 11 ms 852 KB Output is correct
12 Correct 13 ms 856 KB Output is correct
13 Correct 13 ms 852 KB Output is correct
14 Correct 11 ms 848 KB Output is correct
15 Execution timed out 630 ms 852 KB Time limit exceeded
16 Halted 0 ms 0 KB -