Codeforces round 660 Problem D

 Problem Statement Link: https://codeforces.com/problemset/problem/1388/D

First of all, we can consider the update operations between some two elements of the array as a directed edge going from current one to the updating one. So, now it has become a graph problem.

For the additional condition given in the input format section, our graph will be a directed acyclic graph (DAG). Now, we can easily see that it will be most profitable to go deeper from a current node when we have performed the operations for each of those nodes which has an edge to the current node.

So, we will start from a node which has indegree 0. Before that we will calculate the topological sort order for our graph. We know that in DAG, if there is a directed edge from some node u to other node v, then u will definitely come before v in the topological sort order.

Now it is okay to run dfs in the topological sort order. While going, deeper we will carry the sum of all previous a[v] in current dfs. We will also push the nodes in a vector as an answer and update the maximum answer by adding this sum. 

If somewhere inside the dfs, the sum for current dfs nodes becomes negative, then we will stop going deeper and also won’t push the current node to the answer vector. We will push such nodes after all those dfs are run and will push them in the reverse of topological sort order.

My solution code:

#include<bits/stdc++.h> #define ll long long #define pb push_back using namespace std; int n; ll a[200005]; ll ta[200005]; int b[200005]; vector<int>adj[200005],topsort; int vis[200005]; int vis2[200005]; int indegree[200005]; void input(); void tdfs(int v){     vis[v]++;     for(int i=0;i<adj[v].size();i++){         int u = adj[v][i];         if(vis[u]==0)tdfs(u);     }     topsort.pb(v); } ll ans; vector<int>nodes; void dfs(int v, ll total){     vis2[v]++;     ta[v] = total;     if(total<0)return;     nodes.pb(v);     for(int i=0;i<adj[v].size();i++){         int u = adj[v][i];         indegree[u]--;         a[u] += ta[v];         if(vis2[u]==0 and total+a[u]>=0 and indegree[u]==0)dfs(u,a[u]);     } } void solve(){     for(int i=1;i<=n;i++){         if(b[i]!=-1)adj[i].pb(b[i]);     }     for(int i=1;i<=n;i++){         if(vis[i]==0)tdfs(i);     }     reverse(topsort.begin(),topsort.end());     for(int i=0;i<n;i++){         int v = topsort[i];         if(vis2[v]==0)dfs(v,a[v]);     }     for(int i=n-1;i>=0;i--){         int u = topsort[i];         ans+=ta[u];         if(ta[u]<0)nodes.pb(u);     }     cout<<ans<<"\n";     for(int i=0;i<n;i++){         cout<<nodes[i];         if(i<n-1)cout<<" ";     }     cout<<"\n"; } void Clear(){ } int main(){     ios::sync_with_stdio(false);     //cin.tie(0);     input();     solve();     Clear(); } void input(){     cin>>n;     for(int i=1;i<=n;i++){         ll x;         cin>>x;         a[i] = x;     }     for(int i=1;i<=n;i++){         int x;         cin>>x;         b[i] = x;         if(x!=-1)indegree[x]++;     } }