oj.uz

Submission #961564

# Submission time Handle Problem Language Result Execution time Memory
961564 2024-04-12T08:11:35 Z blacktulip Restore Array (RMI19_restore) C++17
0 / 100
 104 ms 1112 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pb push_back
#define fi first
#define se second
 
const int li=500005;
int x[li],y[li],w[li],c[li],n,m;
vector<pair<int,pair<int,int>>> v;
 
void bellman_ford(){
	for(int j=1;j<=n+1;j++){
		for(auto go:v){
			if(c[go.fi]+go.se.se<c[go.se.fi]){
				if(j==n+1){cout<<"-1\n";exit(0);}
				c[go.se.fi]=c[go.fi]+go.se.se;
			}
		}
	}
}
 
int32_t main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		v.pb({i,{i+1,1}});
		v.pb({i+1,{i,0}});
	}
	for(int i=1;i<=m;i++){
		int l,r,k,value;
		cin>>l>>r>>k>>value;
		if(value==0){
			v.pb({l,{r+1,r-l+1-k}});
		}
		else v.pb({r+1,{l,r-l+1-k+1}});
	}
	c[0]=0;
	for(int i=1;i<=n;i++)c[i]=100000000000000;
	bellman_ford();
	for(int i=1;i<=n;i++){
		cout<<c[i]-c[i-1]<<" ";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1112 KB Output is correct
2 Correct 102 ms 1108 KB Output is correct
3 Correct 103 ms 1108 KB Output is correct
4 Incorrect 104 ms 1112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1112 KB Output is correct
2 Correct 102 ms 1108 KB Output is correct
3 Correct 103 ms 1108 KB Output is correct
4 Incorrect 104 ms 1112 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -