Submission #313834

#	Time	Username	Problem	Language	Result	Execution time	Memory
313834		MKopchev	Restore Array (RMI19_restore)	C++14	100 / 100	387 ms	1012 KiB

restore

#include<bits/stdc++.h>
using namespace std;

const int nmax=5e3+42;

struct edge
{
    int u,v,cost;
};
vector<edge> all;

int n,q;

int dist[nmax];

void bellman()
{
    for(int i=1;i<=n;i++)dist[i]=1e9;

    for(int t=0;t<=n;t++)
    {
        for(auto w:all)
            if(dist[w.u]+w.cost<dist[w.v])
            {
                dist[w.v]=dist[w.u]+w.cost;

                //cout<<"update "<<w.u<<" "<<w.v<<" "<<w.cost<<endl;

                //for(int j=0;j<=n;j++)cout<<dist[j]<<" ";cout<<endl;
            }

        //for(int j=0;j<=n;j++)cout<<dist[j]<<" ";cout<<endl;
    }
    for(auto w:all)
        if(dist[w.u]+w.cost<dist[w.v])
        {
            printf("-1\n");
            exit(0);
        }

    for(int i=1;i<=n;i++)
        printf("%i ",dist[i]-dist[i-1]);
    printf("\n");
}

int main()
{
    scanf("%i%i",&n,&q);

    for(int i=0;i<n;i++)
    {
        edge cur;

        cur.u=i;
        cur.v=i+1;
        cur.cost=1;
        all.push_back(cur);

        cur.u=i+1;
        cur.v=i;
        cur.cost=0;
        all.push_back(cur);
    }

    for(int i=1;i<=q;i++)
    {
        edge cur;

        int l,r,k,val;

        scanf("%i%i%i%i",&l,&r,&k,&val);
        l++;
        r++;

        if(val==0)
        {
            cur.u=l-1;
            cur.v=r;
            cur.cost=(r-l+1)-(k+1)+1;
            all.push_back(cur);
        }
        else
        {
            cur.u=r;
            cur.v=l-1;
            cur.cost=-((r-l+1)-(k-1));
            all.push_back(cur);
        }
    }
    /*
    for(auto w:all)
        cout<<w.u<<" "<<w.v<<" "<<w.cost<<endl;
    */
    bellman();

    return 0;
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%i%i",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~
restore.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         scanf("%i%i%i%i",&l,&r,&k,&val);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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