Submission #478954

#	Time	Username	Problem	Language	Result	Execution time	Memory
478954		stefantaga	Restore Array (RMI19_restore)	C++14	100 / 100	581 ms	26164 KiB

restore

#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()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #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";
                    exit(0);
                }
                q.push(x);
            }
        }
    }
    for (i=1;i<=n;i++)
    {
        cout<<dist[i]-dist[i-1]<<" ";
    }
    return 0;
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:47: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]
   47 |         for (int i=0;i<gr[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~~

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