oj.uz

답안 #341553

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341553 2020-12-30T01:01:53 Z Gajowy Restore Array (RMI19_restore) C++14
0 / 100
 366 ms 1132 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(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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 1004 KB Output is correct
2 Correct 343 ms 1004 KB Output is correct
3 Correct 331 ms 1012 KB Output is correct
4 Incorrect 366 ms 1132 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 1004 KB Output is correct
2 Correct 343 ms 1004 KB Output is correct
3 Correct 331 ms 1012 KB Output is correct
4 Incorrect 366 ms 1132 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 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 -