Submission #296646

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
296646	2020-09-10 17:56:19	Pajaraja	Restore Array (RMI19_restore)	C++17	100 / 100	402 ms	892 KiB

restore

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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]); 
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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