fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9;
  5. vector<vector<pair<int, int>>> adj;
  6. vector<int> energy;
  7. vector<bool> visited;
  8. bool impossible;
  9.  
  10. void dfs(int node) {
  11.     visited[node] = true;
  12.     for (auto &edge : adj[node]) {
  13.         int next_node = edge.first;
  14.         int weight = edge.second;
  15.         if (energy[next_node] == INF) {
  16.             energy[next_node] = energy[node] + weight;
  17.             dfs(next_node);
  18.         } else if (energy[next_node] != energy[node] + weight) {
  19.             impossible = true;
  20.         }
  21.     }
  22. }
  23.  
  24. int solve(int n, int m) {
  25.     adj.clear();
  26.     energy.assign(n + 1, INF);
  27.     visited.assign(n + 1, false);
  28.     adj.resize(n + 1);
  29.     impossible = false;
  30.  
  31.     for (int i = 0; i < m; ++i) {
  32.         int u, v, b;
  33.         cin >> u >> v >> b;
  34.         if (b == 1) {
  35.             adj[u].emplace_back(v, 1);
  36.             adj[v].emplace_back(u, -1);
  37.         } else {
  38.             adj[u].emplace_back(v, 1);
  39.             adj[v].emplace_back(u, 1);
  40.         }
  41.     }
  42.  
  43.     for (int i = 1; i <= n; ++i) {
  44.         if (!visited[i]) {
  45.             energy[i] = 0;
  46.             dfs(i);
  47.         }
  48.     }
  49.  
  50.     if (impossible) {
  51.         return -1;
  52.     }
  53.  
  54.     int min_energy = INF, max_energy = -INF;
  55.     for (int i = 1; i <= n; ++i) {
  56.         if (energy[i] != INF) {
  57.             min_energy = min(min_energy, energy[i]);
  58.             max_energy = max(max_energy, energy[i]);
  59.         }
  60.     }
  61.  
  62.     return max_energy - min_energy;
  63. }
  64.  
  65. int main() {
  66.     int t;
  67.     cin >> t;
  68.     while (t--) {
  69.         int n, m;
  70.         cin >> n >> m;
  71.         int result = solve(n, m);
  72.         if (result == -1) {
  73.             cout << "Impossible to form a stellar gradient with the given configuration." << endl;
  74.         } else {
  75.             cout << "Maximum stellar gradient: " << result << endl;
  76.         }
  77.     }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1
5 5
1 2 1
2 3 0
3 4 1
4 5 0
5 1 0
stdout
copy 
Impossible to form a stellar gradient with the given configuration.
https://ideone.com/19Qmpw
language:
C++14 (clang 8.0)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!