Submission #646825

#TimeUsernameProblemLanguageResultExecution timeMemory
646825andrei_c1Restore Array (RMI19_restore)C++17
7 / 100
639 ms936 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL ifstream fin("restore.in"); ofstream fout("restore.out"); #else #define fin cin #define fout cout #endif const int NMAX = 5000; const int INF = 1e9; int n, m; vector<pair<int, int>> adj[NMAX + 1]; int dist[NMAX + 1], freq[NMAX + 1]; bool inQ[NMAX + 1]; bool bell(int u) { fill(dist, dist + n + 1, INF); fill(inQ, inQ + n + 1, 0); queue<int> q; q.push(u); dist[u] = 0; inQ[u] = 1; while(!q.empty()) { int v = q.front(); q.pop(); inQ[v] = 0; for(const auto it: adj[v]) { if(dist[it.first] > dist[v] + it.second) { dist[it.first] = dist[v] + it.second; if(!inQ[it.first]) { q.push(it.first); inQ[it.first] = 1; } if(++freq[it.first] >= n + 1 && dist[it.first] < 0) { return 0; } } } } return 1; } int main() { ios_base :: sync_with_stdio(0); fin.tie(nullptr); fin >> n >> m; for(int i = 1; i <= m; i++) { int l, r, k, value; fin >> l >> r >> k >> value; l++; r++; if(value == 0) { adj[l - 1].push_back({r, r - l + 1 - k}); } else { adj[r].push_back({l - 1, -(r - l + 1) + k - 1}); } } for(int i = 1; i <= n; i++) { adj[i - 1].push_back({i, 1}); adj[i].push_back({i - 1, -0}); } if(bell(0)) { for(int i = 1; i <= n; i++) { fout << dist[i] - dist[i - 1] << " "; } fout << '\n'; } else { fout << "-1\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...