oj.uz

Submission #470170

# Submission time Handle Problem Language Result Execution time Memory
470170 2021-09-03T07:23:58 Z radal Watermelon (INOI20_watermelon) C++14
0 / 100
 2000 ms 538164 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];
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[500];
    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{
                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 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 4 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 4 ms 4940 KB Output is correct
12 Incorrect 3 ms 5028 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9672 KB Output is correct
2 Correct 752 ms 156572 KB Output is correct
3 Correct 32 ms 9800 KB Output is correct
4 Correct 455 ms 136992 KB Output is correct
5 Correct 31 ms 9972 KB Output is correct
6 Correct 32 ms 9960 KB Output is correct
7 Correct 32 ms 9772 KB Output is correct
8 Correct 33 ms 9876 KB Output is correct
9 Correct 31 ms 9800 KB Output is correct
10 Correct 30 ms 9804 KB Output is correct
11 Correct 66 ms 14784 KB Output is correct
12 Correct 61 ms 14608 KB Output is correct
13 Correct 62 ms 14660 KB Output is correct
14 Correct 62 ms 14688 KB Output is correct
15 Correct 1824 ms 516764 KB Output is correct
16 Execution timed out 2121 ms 538164 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9672 KB Output is correct
2 Correct 752 ms 156572 KB Output is correct
3 Correct 32 ms 9800 KB Output is correct
4 Correct 455 ms 136992 KB Output is correct
5 Correct 31 ms 9972 KB Output is correct
6 Correct 32 ms 9960 KB Output is correct
7 Correct 32 ms 9772 KB Output is correct
8 Correct 33 ms 9876 KB Output is correct
9 Correct 31 ms 9800 KB Output is correct
10 Correct 30 ms 9804 KB Output is correct
11 Correct 66 ms 14784 KB Output is correct
12 Correct 61 ms 14608 KB Output is correct
13 Correct 62 ms 14660 KB Output is correct
14 Correct 62 ms 14688 KB Output is correct
15 Correct 1824 ms 516764 KB Output is correct
16 Execution timed out 2121 ms 538164 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

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