제출 #1125972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125972		alir3za_zar3	Restore Array (RMI19_restore)	C++20	100 / 100	430 ms	936 KiB

restore

// Alir3za.Zar3 -> Shiraz , Iran 
#include <bits/stdc++.h> 
using namespace std; 
#define loop(i , l , r) for (int i=l; i<=r; i+=1) 
#define arc(i , r , l) for (int i=r; i>=l; i-=1) 
#define Turbo_In_Out ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define Tc_Management int Tc;cin>>Tc;while(Tc--) 
const int N = 5e3+10 , M = 1e4+10 , Inf = 1e9; 
int n,m,q[N]; 
vector<pair<int,int>> e[N]; 
bool Bellman_Ford () { 
  fill_n(q,N,Inf); q[0] = 0; 
  int op; loop(k,1,n+5) { 
    op = 0; loop(v,0,n) { 
      for (auto [to,w] : e[v]) { 
        if (q[to]>q[v]+w) { ++op; q[to]=q[v]+w; } 
        
      } 
    } if (op==0){ break; } 
  } if (op){ return 1; } 
  return 0; 
} signed main(){
  Turbo_In_Out 
  cin >> n >> m; 
  loop(i,1,n) { 
    e[i-1].push_back({i,1}); 
    e[i].push_back({i-1,0});
  } loop(i,1,m) { 
    int l,r,k,v;
    cin >> l >> r >> k >> v;
    int len = r-l+1; ++r; 
    if (v){ e[r].push_back({l,k-len-1}); } 
    else { e[l].push_back({r,len-k}); } 
  } if (Bellman_Ford()) {
    cout << -1 << '\n'; return 0; }
    loop(i,1,n) { cout << q[i]-q[i-1] << " "; } 
    cout << '\n'; 
}

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