#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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]=n;
}
maxvals[0]=0;
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&&maxvals[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];
}
reverse(ans.begin(),ans.end());
vector<int> s(n+1,0);
for (int i = 1; i<=n; i++){
s[i]=s[i-1]+ans[i-1];
//cout<<minvals[i]<<' '<<maxvals[i]<<' '<<s[i]<<'\n';
assert(minvals[i]<=s[i]&&s[i]<=maxvals[i]);
}
for (int i = 0; i<m; i++){
assert(s[a[i]]>=s[b[i]]+c[i]);
}
for (int i = 0; i<n; i++){
cout<<ans[i]<<' ';
}cout<<'\n';
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
/*if (n<=18){
subtask1();
} else {*/
relaxedges();
//}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
290 ms |
199160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
290 ms |
199160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
