oj.uz

Submission #470172

# Submission time Handle Problem Language Result Execution time Memory
470172 2021-09-03T07:30:05 Z radal Watermelon (INOI20_watermelon) C++14
0 / 100
 2000 ms 743248 KB 
#include <bits/stdc++.h>
#define rep(i,l,r) for (int i = l; i < r; i++)
#define pb push_back
#define debug(x) cerr << #x <<  " : " << x << endl;
using namespace std;

typedef long long ll;

const ll N = 1e5+20;
int b[N];
int n,k;
int vis[N],din[N],a[N];
bool fl[N];
vector<int> in[N],out[N];
bool dfs(int v){
    vis[v] = 1;
    for (int u : out[v]){
        if(vis[u] == 1) return 0;
        if (!vis[u] && !dfs(u)) return 0;
    }
    vis[v] = 2;
    return 1;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    rep(i,1,n+1) cin >> b[i];
    if (b[n] != -1){
        cout << -1;
        return 0;
    }
    vector<int> ve[300];
    int sz = n,p = 1;
    rep(i,1,n+1)
        ve[1].pb(i);
    while (true){
        if (!sz) break;
        bool f = 1;
        rep(i,0,sz){
            f &= (b[ve[p][i]] == -1);
            if (b[ve[p][i]] != p){
                ve[p+1].pb(ve[p][i]);
                if (i != sz-1){
                    in[ve[p][i+1]].pb(ve[p][i]);
                    out[ve[p][i]].pb(ve[p][i+1]);
                }
            }
            else if(!fl[ve[p][i]]){
                if (b[ve[p][i]] == -1 && b[ve[p][i+1]] == -1) fl[ve[p][i]] = 1;
                in[ve[p][i]].pb(ve[p][i+1]);
                out[ve[p][i+1]].pb(ve[p][i]);
            }
        }
        if (f){
            rep(i,1,sz){
                in[ve[p][i]].pb(ve[p][i-1]);
                out[ve[p][i-1]].pb(ve[p][i]);
            }
            break;
        }
        p++;
        if ((int)ve[p].size() == sz){
            cout << -1;
            return 0;
        }
        sz = ve[p].size();
    }
    priority_queue<int> pq;
    rep(i,1,n+1){
        if (!vis[i]){
            if (!dfs(i)){
                cout << -1;
                return 0;
            }
        }
        din[i] = out[i].size();
        if (!din[i])
            pq.push(-i);
    }
    p = 1;
    while (!pq.empty()){
        int v = -pq.top();
        pq.pop();
        a[v] = p;
        for (int u : in[v]){
            din[u]--;
            if (!din[u]) pq.push(-u);
        }
        p++;
    }
    rep(i,1,n+1) cout << a[i] << ' ';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Incorrect 3 ms 4940 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Incorrect 3 ms 4940 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9728 KB Output is correct
2 Correct 730 ms 156340 KB Output is correct
3 Correct 30 ms 9808 KB Output is correct
4 Correct 468 ms 136896 KB Output is correct
5 Correct 31 ms 9940 KB Output is correct
6 Correct 37 ms 9912 KB Output is correct
7 Correct 30 ms 9860 KB Output is correct
8 Correct 31 ms 9852 KB Output is correct
9 Correct 36 ms 9844 KB Output is correct
10 Correct 29 ms 9800 KB Output is correct
11 Correct 61 ms 14676 KB Output is correct
12 Correct 61 ms 14628 KB Output is correct
13 Correct 69 ms 14884 KB Output is correct
14 Correct 65 ms 14768 KB Output is correct
15 Correct 1793 ms 516732 KB Output is correct
16 Execution timed out 2107 ms 743248 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9728 KB Output is correct
2 Correct 730 ms 156340 KB Output is correct
3 Correct 30 ms 9808 KB Output is correct
4 Correct 468 ms 136896 KB Output is correct
5 Correct 31 ms 9940 KB Output is correct
6 Correct 37 ms 9912 KB Output is correct
7 Correct 30 ms 9860 KB Output is correct
8 Correct 31 ms 9852 KB Output is correct
9 Correct 36 ms 9844 KB Output is correct
10 Correct 29 ms 9800 KB Output is correct
11 Correct 61 ms 14676 KB Output is correct
12 Correct 61 ms 14628 KB Output is correct
13 Correct 69 ms 14884 KB Output is correct
14 Correct 65 ms 14768 KB Output is correct
15 Correct 1793 ms 516732 KB Output is correct
16 Execution timed out 2107 ms 743248 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Incorrect 3 ms 4940 KB Output isn't correct
13 Halted 0 ms 0 KB -