oj.uz

Submission #568164

# Submission time Handle Problem Language Result Execution time Memory
568164 2022-05-24T19:00:25 Z birthdaycake Restore Array (RMI19_restore) C++17
0 / 100
 68 ms 5524 KB 
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
 
 

vector<pair<int,int>>adj[200001];
int dist[200001];
signed main(){
    
    boost;
    
    int n,m; cin >> n >> m;
    vector<pair<int,pair<int,int>>>d;
    for(int i = 0; i < m; i++){
        int l,r,k,v; cin >> l >> r >> k >> v;
        l++; r++;
        int a = r - l + 2 - k, b = r - l + 1 - k;
        if(v == 1){
            d.push_back({r,{l - 1, -a}});
        }else{
            d.push_back({l - 1, {r,b}});
        }
    }
    for(int i = 0; i < n; i++){
        adj[i].push_back({i + 1, 1});
        adj[i + 1].push_back({i, 0});
    }
    for(int i = 1; i <= n; i++) dist[i] = 1e18;
    
    dist[0] = 0;
    for(int i = 0; i < n + 1; i++){
        for(auto s:d){
            if(dist[s.first] != 1e18 && dist[s.first] + s.second.second < dist[s.second.first]){
                dist[s.second.first] = dist[s.first] + s.second.second;
                if(i == n - 1){
                    cout << "-1";
                    return 0;
                }
            }
        }
    }
    int x = 0;
    for(int i = 1; i <= n; i++){
        if(dist[i] > x){
            x++;
            cout << "1";
        }else{
            cout << "0";
        }
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Integer 10011111 violates the range [-1, 1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 5524 KB Expected integer, but "111111111111111111111111111111...1111111111111111111111111111111" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 5524 KB Expected integer, but "111111111111111111111111111111...1111111111111111111111111111111" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Integer 10011111 violates the range [-1, 1]
2 Halted 0 ms 0 KB -