| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 270576 | 2020-08-17T18:46:23 Z | eohomegrownapps | Restore Array (RMI19_restore) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
int n,m;
void relaxedges(){
int a[15000], b[15000], c[15000];
for (int i = 0; i<m; i++){
int l,r,k,v;
cin>>l>>r>>k>>v;
r++;
if (v==0){
a[i]=l;
b[i]=r;
c[i]=k-(r-l);
} else {
a[i]=r;
b[i]=l;
c[i]=(r-l)-k+1;
}
}
bool changed = true;
bool works = true;
int minvals[15000], maxvals[15000];
for (int i = 0; i<=n; i++){
minvals[i]=0;
maxvals[i]=i;
}
while (changed&&works){
changed=false;
for (int i = 0; i<m; i++){
if (minvals[b[i]]+c[i]>minvals[a[i]]){
changed=true;
minvals[a[i]]=minvals[b[i]]+c[i];
}
if (maxvals[a[i]]-c[i]<maxvals[b[i]]){
changed=true;
maxvals[b[i]]=maxvals[a[i]]-c[i];
}
if (minvals[a[i]]>maxvals[a[i]]){
works=false;
}
if (minvals[b[i]]>maxvals[b[i]]){
works=false;
}
}
}
if (!works){
cout<<-1<<'\n';
return;
}
/*for (int i = 0; i<=n; i++){
cout<<minvals[i]<<' '<<maxvals[i]<<'\n';
}*/
vector<vector<int>> parent(n+1,vector<int>(n+1,-1));
assert(minvals[0]==0&&maxvasls[0]==0);
parent[0][0]=0;
int ind = 0;
for (int y = 1; y<=n; y++){
bool works = false;
for (int x = minvals[y]; x<=maxvals[y]; x++){
if (x-1>=0){
if (parent[y-1][x-1]!=-1){
parent[y][x]=x-1;
works=true;
ind = x;
}
}
if (parent[y-1][x]!=-1){
parent[y][x]=x;
works=true;
ind = x;
}
}
if (!works){
cout<<-1<<'\n';
return;
}
}
/*for (int y = 0; y<=n; y++){
for (int x = 0; x<=n; x++){
cout<<parent[y][x]<<' ';
}cout<<'\n';
}*/
vector<bool> ans;
for (int i = n; i>0; i--){
if (ind==parent[i][ind]){
ans.push_back(0);
} else {
ans.push_back(1);
}
ind=parent[i][ind];
}
for (int i = n-1; i>=0; i--){
cout<<ans[i]<<' ';
}cout<<'\n';
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
cout<<-1<<'\n';
/*if (n<=18){
subtask1();
} else {*/
relaxedges();
//}
}