Submission #296646

#	Time	Username	Problem	Language	Result	Execution time	Memory
296646		Pajaraja	Restore Array (RMI19_restore)	C++17	100 / 100	402 ms	892 KiB

restore

#include <bits/stdc++.h>
#define MAXN 5007
using namespace std;
int dist[MAXN],dn[MAXN],ep[10*MAXN],ek[10*MAXN],ev[10*MAXN],br;
int n,m;
void zvonocovek() {for(int i=0;i<br;i++) dist[ek[i]]=min(dist[ek[i]],dist[ep[i]]+ev[i]);}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++) {ek[br]=i; ep[br]=i+1; ev[br]=0; br++;}
	for(int i=0;i<n;i++) {ek[br]=i+1; ep[br]=i; ev[br]=1; br++;}
	for(int i=0;i<m;i++)
	{
		int a,b,k,v; cin>>a>>b>>k>>v; a++; b++;
		if(v==0) {ek[br]=b; ep[br]=a-1; ev[br]=b+1-a-k; br++;} 
		else {ek[br]=a-1; ep[br]=b; ev[br]=k+a-2-b; br++;}
	}
	for(int i=1;i<=n;i++) dist[i]=1000000000;
	for(int i=0;i<n;i++) zvonocovek();
	for(int i=0;i<=n;i++) dn[i]=dist[i];
	zvonocovek();
	for(int i=0;i<=n;i++) if(dn[i]!=dist[i]) {printf("-1"); return 0;}
	for(int i=0;i<n;i++) printf("%d ",dist[i+1]-dist[i]); 
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55