oj.uz

Submission #478952

# Submission time Handle Problem Language Result Execution time Memory
478952 2021-10-09T07:48:58 Z stefantaga Restore Array (RMI19_restore) C++14
7 / 100
 600 ms 24784 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m,i,j,st,dr,val,k,dist[50005],cnt_push[50005];
vector <pair <int,int> > gr[50000];
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>st>>dr>>k>>val;
        st++;
        dr++;
        if (val==0)
        {
            k=dr-st+1-k;
            gr[st-1].push_back({dr,k});
        }
        else
        {
            k=dr-st+1-k+1;
            gr[dr].push_back({st-1,-k});
        }
    }
    for (i=0;i<=n;i++)
    {
        dist[i]=1e9;
    }
    for (i=1;i<=n;i++)
    {
        gr[i].push_back({i-1,0});
        gr[i-1].push_back({i,1});
    }
    queue <int> q;
    q.push(0);
    dist[0]=0;
    while (!q.empty())
    {
        int node=q.front();
        q.pop();
        for (int i=0;i<gr[node].size();i++)
        {
            int x=gr[node][i].first;
            if (dist[node]+gr[node][i].second<dist[x])
            {
                dist[x]=dist[node]+gr[node][i].second;
                if (++cnt_push[x]>n)
                {
                    cout<<"-1";
                    return 0;
                }
                q.push(x);
            }
        }
    }
    for (i=1;i<=n;i++)
    {
        cout<<dist[i]-dist[i-1]<<" ";
    }
    return 0;
}

Compilation message

restore.cpp: In function 'int main()':
restore.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i=0;i<gr[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1432 KB Output is correct
3 Correct 1 ms 1488 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1476 KB Output is correct
6 Correct 2 ms 1488 KB Output is correct
7 Correct 1 ms 1488 KB Output is correct
8 Correct 1 ms 1488 KB Output is correct
9 Correct 1 ms 1488 KB Output is correct
10 Correct 1 ms 1488 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1924 KB Output is correct
2 Correct 24 ms 1872 KB Output is correct
3 Correct 21 ms 1948 KB Output is correct
4 Correct 19 ms 1872 KB Output is correct
5 Correct 600 ms 24660 KB Output is correct
6 Execution timed out 605 ms 24784 KB Time limit exceeded

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1924 KB Output is correct
2 Correct 24 ms 1872 KB Output is correct
3 Correct 21 ms 1948 KB Output is correct
4 Correct 19 ms 1872 KB Output is correct
5 Correct 600 ms 24660 KB Output is correct
6 Execution timed out 605 ms 24784 KB Time limit exceeded

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1432 KB Output is correct
3 Correct 1 ms 1488 KB Output is correct
4 Correct 1 ms 1360 KB Output is correct
5 Correct 1 ms 1476 KB Output is correct
6 Correct 2 ms 1488 KB Output is correct
7 Correct 1 ms 1488 KB Output is correct
8 Correct 1 ms 1488 KB Output is correct
9 Correct 1 ms 1488 KB Output is correct
10 Correct 1 ms 1488 KB Output is correct
11 Correct 23 ms 1924 KB Output is correct
12 Correct 24 ms 1872 KB Output is correct
13 Correct 21 ms 1948 KB Output is correct
14 Correct 19 ms 1872 KB Output is correct
15 Correct 600 ms 24660 KB Output is correct
16 Execution timed out 605 ms 24784 KB Time limit exceeded