Submission #470170

#TimeUsernameProblemLanguageResultExecution timeMemory
470170radalWatermelon (INOI20_watermelon)C++14
0 / 100
2121 ms538164 KiB
#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] << ' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...