Cod sursă (job #816414)

// Metodă: Generăm componentele tare conexe cu algoritmul lui Kosaraju. Acesta
// le emite în ordine topologică. Apoi rulăm o programare dinamică înapoi:
// fiecare componentă obține profitul propriu + profitul maxim venit dinspre
// stînga din orice componentă accesibilă din h.
//
// v2: Programare dinamică înapoi.
#include <stdio.h>
#include <vector>

const int MAX_NODES = 100'000;

struct node {
  std::vector<int> adj, adjt;
  int comp;
  short cost;
  bool mark;
};

struct component {
  std::vector<int> pred; // lista predecesorilor
  int profit;
};

node nd[MAX_NODES + 1];
component scc[MAX_NODES + 1];
int order[MAX_NODES];
int n, hotel, num_scc;

void read_graph() {
  FILE* f = fopen("risipa.in", "r");
  int m, u, v;
  fscanf(f, "%d %d %d", &n, &m, &hotel);
  for (u = 1; u <= n; u++) {
    fscanf(f, "%hd", &nd[u].cost);
  }

  while (m--) {
    fscanf(f, "%d %d", &u, &v);
    nd[u].adj.push_back(v);
    nd[v].adjt.push_back(u);
  }
  fclose(f);
}

void dfs(int u) {
  nd[u].mark = true;
  for (auto v: nd[u].adj) {
    if (!nd[v].mark) {
      dfs(v);
    }
  }

  static int time_out = 0;
  order[time_out++] = u;
}

// DFS #1: Colectează nodurile în ordinea timpilor de ieșire.
void dfs_driver() {
  for (int u = 1; u <= n; u++) {
    if (!nd[u].mark) {
      dfs(u);
    }
  }
}

void tdfs(int u) {
  nd[u].mark = false;
  nd[u].comp = num_scc;
  scc[num_scc].profit += nd[u].cost;

  for (auto v: nd[u].adjt) {
    if (nd[v].mark) {
      tdfs(v);
    }
  }
}

// DFS #2 pe graful de mai sus în ordinea descrescătoare a timpilor de ieșire.
void transpose_dfs_driver() {
  for (int i = n - 1; i >= 0; i--) {
    int u = order[i];
    if (nd[u].mark) {
      tdfs(u);
      num_scc++;
    }
  }
}

void build_scc_graph() {
  for (int u = 1; u <= n; u++) {
    for (int v: nd[u].adj) {
      int cu = nd[u].comp, cv = nd[v].comp;
      if (cu != cv) {
        scc[cv].pred.push_back(cu);
      }
    }
  }
}

void compute_scc_profits()  {
  for (int i = 0; i < num_scc; i++) {
    int incoming = 0;
    for (int p: scc[i].pred) {
      incoming = std::max(incoming, scc[p].profit);
    }
    if (incoming || nd[hotel].comp == i) {
      scc[i].profit += incoming;
    } else {
      // ignoră chiar și propriul profit, căci este inaccesibilă
      scc[i].profit = 0;
    }
  }
}

void write_answers() {
  FILE* f = fopen("risipa.out", "w");
  for (int u = 1; u <= n; u++) {
    fprintf(f, "%d\n", scc[nd[u].comp].profit);
  }
  fclose(f);
}
int main() {
  read_graph();
  dfs_driver();
  transpose_dfs_driver();
  build_scc_graph();
  compute_scc_profits();
  write_answers();

  return 0;
}