oj.uz

Submission #341554

# Submission time Handle Problem Language Result Execution time Memory
341554 2020-12-30T01:04:30 Z Gajowy Restore Array (RMI19_restore) C++14
0 / 100
 337 ms 1004 KB 
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
#define e1 first
#define e2 second

const int MAXN=5e3+10;
const int inf=1e9+2137;

vector<pair<int,int>> g[MAXN];

int d[MAXN];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		d[i]=inf;
		g[i-1].eb(mp(i,1));
		g[i].eb(mp(i-1,0));
	}
	while(m--){
		int l,r,k,v;
		cin>>l>>r>>k>>v;
		l++,r++;
		if(v==0){
			g[l-1].eb(mp(r,r-l+1-k));
		}
		else{
			g[r].eb(mp(l-1,r-l+2-k));
		}
	}
	int lastRelax=0;
	for(int i=0;i<=n;i++){
		for(int u=0;u<=n;u++)
			for(auto v:g[u])
				if(d[u]+v.e2<d[v.e1]){
					d[v.e1]=d[u]+v.e2,lastRelax=i;
					if(d[v.e1]<0){
						cout<<"-1\n";
						return 0;
					}
				}
	}
	if(lastRelax==n){
		cout<<"-1\n";
		return 0;
	}
	else{
		for(int i=1;i<=n;i++)
			cout<<(d[i]-d[i-1])<<' ';
		cout<<'\n';
	}
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 1004 KB Output is correct
2 Correct 317 ms 892 KB Output is correct
3 Correct 327 ms 876 KB Output is correct
4 Incorrect 337 ms 876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 1004 KB Output is correct
2 Correct 317 ms 892 KB Output is correct
3 Correct 327 ms 876 KB Output is correct
4 Incorrect 337 ms 876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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