oj.uz

답안 #1092534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092534 2024-09-24T10:35:19 Z May27_th Restore Array (RMI19_restore) C++17
0 / 100
 85 ms 860 KB 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 10;
const i64 INF = 1e18;
void Solve(void) {  
  int N, M; cin >> N >> M;
  vector<array<int, 3>> edges;
  for (int i = 0; i <= N; i ++) {
    edges.pb({N + 1, i, 0});
  }
  for (int i = 0; i < M; i ++) {
    int l, r, k, v; cin >> l >> r >> k >> v;
    r ++;
    if (v == 0) edges.pb({r, l, -k});
    else edges.pb({l, r, k - 1});
  }
  // Add new vertex N + 1 to the graph -> cnt[i] = shortest path from N + 1 to i;
  vector<i64> d(N + 5, INF); d[N + 1] = 0;
  int x = -1;
  for (int i = 0; i < N; i ++) {
    x = -1;
    for (auto [u, v, w] : edges) {
      // cout << u << " " << v << " " << w << "\n";
      if (d[u] < INF) {
        if (d[u] + w < d[v]) {
          x = v;
          d[v] = max(-INF, d[u] + w);
        }
      }
    }
  }

  if (x != -1) {
    cout << -1 << "\n";
    return;
  }
  for (int i = 1; i <= N; i ++) {
    d[i] -= d[0];
    if (d[i] > d[i - 1]) cout << 0 << " ";
    else cout << 1 << " ";    
  } 
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -