Cod sursă (job #816412)

// Ne prefacem că nu știm algoritmii de componente tare conexe. Rulăm cîte o
// parcurgere DFS din fiecare nod ca să construim matricea de accesibilitate.
#include <queue>
#include <stdio.h>
#include <vector>

const int MAX_NODES = 1'000;

struct node {
  std::vector<int> adj;
  int cost;
  int comp;
};

struct component {
  std::vector<int> adj;
  int in_degree;
  bool reachable_from_h;
  int cost;
  int total;
};

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

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].cost);
  }

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

void dfs(int u, int src) {
  reach[src][u] = true;

  for (int v: nd[u].adj) {
    if (!reach[src][v]) {
      dfs(v, src);
    }
  }
}

void dfs_wrapper() {
  for (int u = 1; u <= n; u++) {
    dfs(u, u);
  }
}

void label_comps() {
  for (int u = 1; u <= n; u++) {
    if (!nd[u].comp) {
      num_scc++;
      // fprintf(stderr, "SCC #%d\n", num_scc);
      for (int v = u; v <= n; v++) {
        if (reach[u][v] && reach[v][u]) {
          nd[v].comp = num_scc;
          scc[num_scc].cost += nd[v].cost;
          // fprintf(stderr, "node %d\n", v);
        }
      }
      // fprintf(stderr, "SCC cost %d\n", scc[num_scc].cost);
    }
  }
}

void condensate() {
  for (int u = 1; u <= n; u++) {
    for (int v: nd[u].adj) {
      int cu = nd[u].comp, cv = nd[v].comp;
      // fprintf(stderr, "Edge %d %d comp %d %d\n", u, v, cu, cv);
      if (cu != cv) {
        scc[cu].adj.push_back(cv);
        scc[cv].in_degree++;
      }
    }
  }
}

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


void propagate_costs(int c) {
  scc[c].reachable_from_h |= (nd[hotel].comp == c);
  // fprintf(stderr, "PROPAGATE %d reachable %d total %d\n", c, scc[c].reachable_from_h, scc[c].total);

  if (scc[c].reachable_from_h) {
    scc[c].total += scc[c].cost;
    for (auto v: scc[c].adj) {
      // fprintf(stderr, "Marking SCC %d as reachable, maximizing its total with %d\n",
      //        v, scc[c].total);
      scc[v].reachable_from_h = true;
      maximize(scc[v].total, scc[c].total);
    }
  }
}

void top_sort_sccs() {
  std::queue<int> q;
  for (int c = 1; c <= num_scc; c++) {
    if (!scc[c].in_degree) {
      q.push(c);
    }
  }

  while (!q.empty()) {
    int c = q.front();
    q.pop();

    propagate_costs(c);

    for (auto v: scc[c].adj) {
      scc[v].in_degree--;
      if (!scc[v].in_degree) {
        q.push(v);
      }
    }
  }
}

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

int main() {
  read_data();
  dfs_wrapper();
  label_comps();
  condensate();
  top_sort_sccs();
  write_answers();

  return 0;
}