Cod sursă (job #816415)

// Metodă: Construim graful transpus, pe care punem întrebarea: care este
// profitul din fiecare nod u pînă în nodul h? Calculăm componentele tare
// conexe cu algoritmul lui Tarjan. Fiecare componentă calculează două valori:
//
// 1. Pe parcursul explorării acelei CTC, profitul maxim pe o muchie externă
// spre o altă CTC care are, la rîndul ei, drum spre h.
//
// 2. La finalul explorării, odată ce cunoaștem nodurile din CTC, suma
// costurilor acelor noduri.
//
// La finalul explorării, propagăm suma celor două valori la fiecare nod din
// CTC, ca să le putem răspunde altor noduri viitoare care au muchii înspre
// această CTC.
#include <stdio.h>
#include <vector>

const int MAX_NODES = 100'000;

struct node {
  std::vector<int> adj;
  int subtree_cost; // costul din magazinele din subarborele DFS
  int total;    // costul maxim pînă în h sau 0 dacă nu putem ajunge în h

  int time;
  int low;
  bool on_stack;
  bool can_reach_h;
};

node nd[MAX_NODES + 1];
int st[MAX_NODES], ss; // stiva DFS
int n, hotel;

void read_data() {
  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, "%d", &nd[u].subtree_cost);
  }

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

void minimize(int& x, int y) {
  if (y < x) {
    x = y;
  }
}

void maximize(int& x, int y) {
  if (y > x) {
    x = y;
  }
}

void pull_cost(int u, int v) {
  maximize(nd[u].total, nd[v].total);
  if (nd[v].on_stack) {
    nd[u].subtree_cost += nd[v].subtree_cost;
    nd[v].subtree_cost = 0; // evită dubla contabilitate
  }
}

void pop_scc(int root) {
  int total = nd[root].can_reach_h
    ? (nd[root].subtree_cost + nd[root].total)
    : 0;

  int v;
  do {
    v = st[--ss];
    nd[v].on_stack = false;
    nd[v].total = total;
    nd[v].can_reach_h = nd[root].can_reach_h;
  } while (v != root);
}

void dfs(int u) {
  static int time = 0;
  nd[u].time = nd[u].low = ++time;
  nd[u].on_stack = true;
  st[ss++] = u;

  nd[u].can_reach_h = (u == hotel);

  for (int v: nd[u].adj) {
    if (!nd[v].time) {
      dfs(v);
      nd[u].can_reach_h |= nd[v].can_reach_h;
      minimize(nd[u].low, nd[v].low);
    } else if (nd[v].on_stack) {
      minimize(nd[u].low, nd[v].time);
    } else {
      nd[u].can_reach_h |= nd[v].can_reach_h;
    }

    pull_cost(u, v);
  }

  if (nd[u].low == nd[u].time) {
    pop_scc(u);
  }
}

void dfs_wrapper() {
  for (int u = 1; u <= n; u++) {
    if (!nd[u].time) {
      dfs(u);
    }
  }
}

void write_answers() {
  FILE* f = fopen("risipa.out", "w");
  for (int u = 1; u <= n; u++) {
    fprintf(f, "%d\n", nd[u].total);
  }
  fclose(f);
}

int main() {
  read_data();
  dfs_wrapper();
  write_answers();

  return 0;
}