This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++)
| ~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |