fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. // Struktura przechowująca stan pojedynczej składowej w grafie
  10. struct Component {
  11.     vector<int> q;                          // Kolejka wierzchołków do przetworzenia
  12.     vector<int> nodes;                      // Wierzchołki należące do tej składowej
  13.     set<int> keys;                          // Zabrane klucze
  14.     map<int, vector<int>> blocked;          // Krawędzie zablokowane: wymagany_klucz -> lista_celów
  15. };
  16.  
  17. int n, m;
  18. vector<int> r;
  19. vector<vector<pair<int, int>>> adj;
  20. vector<int> parent_node;
  21. vector<int> state; // 0: NIEODWIEDZONE, 1: AKTYWNE (w stosie), 2: ZAKOŃCZONE
  22. vector<bool> is_sink;
  23. vector<int> sz;
  24. vector<bool> expanded;
  25. vector<Component*> comps;
  26.  
  27. // Struktura Zbiorów Rozłącznych (DSU) z kompresją ścieżki
  28. int find_set(int v) {
  29.     if (v == parent_node[v]) return v;
  30.     return parent_node[v] = find_set(parent_node[v]);
  31. }
  32.  
  33. // Funkcja łącząca dwie składowe (Small-To-Large Merging)
  34. int merge_components(int u, int v) {
  35.     u = find_set(u);
  36.     v = find_set(v);
  37.     if (u == v) return u;
  38.  
  39.     int size_u = comps[u]->nodes.size() + comps[u]->keys.size() + comps[u]->blocked.size();
  40.     int size_v = comps[v]->nodes.size() + comps[v]->keys.size() + comps[v]->blocked.size();
  41.  
  42.     // Zapewniamy, że dołączamy mniejszy do większego (dla wydajności O(N log^2 N))
  43.     if (size_u < size_v) {
  44.         swap(u, v);
  45.     }
  46.  
  47.     for (int node : comps[v]->nodes) {
  48.         comps[u]->nodes.push_back(node);
  49.     }
  50.  
  51.     for (int key : comps[v]->keys) {
  52.         if (comps[u]->keys.find(key) == comps[u]->keys.end()) {
  53.             comps[u]->keys.insert(key);
  54.             auto it = comps[u]->blocked.find(key);
  55.             if (it != comps[u]->blocked.end()) {
  56.                 for (int nxt : it->second) comps[u]->q.push_back(nxt);
  57.                 comps[u]->blocked.erase(it);
  58.             }
  59.         }
  60.     }
  61.  
  62.     for (auto& pair : comps[v]->blocked) {
  63.         int key = pair.first;
  64.         if (comps[u]->keys.find(key) != comps[u]->keys.end()) {
  65.             for (int nxt : pair.second) comps[u]->q.push_back(nxt);
  66.         } else {
  67.             auto& u_vec = comps[u]->blocked[key];
  68.             if (u_vec.empty()) {
  69.                 u_vec = move(pair.second);
  70.             } else {
  71.                 u_vec.insert(u_vec.end(), pair.second.begin(), pair.second.end());
  72.             }
  73.         }
  74.     }
  75.  
  76.     for (int q_item : comps[v]->q) {
  77.         comps[u]->q.push_back(q_item);
  78.     }
  79.  
  80.     parent_node[v] = u;
  81.     delete comps[v]; // Zwalniamy pamięć
  82.     comps[v] = nullptr;
  83.  
  84.     return u;
  85. }
  86.  
  87. int main() {
  88.     // Optymalizacja wejścia/wyjścia
  89.     ios_base::sync_with_stdio(false);
  90.     cin.tie(NULL);
  91.  
  92.     if (!(cin >> n >> m)) return 0;
  93.  
  94.     r.resize(n);
  95.     for (int i = 0; i < n; ++i) cin >> r[i];
  96.  
  97.     adj.resize(n);
  98.     for (int i = 0; i < m; ++i) {
  99.         int u, v, c;
  100.         cin >> u >> v >> c;
  101.         adj[u].push_back({v, c});
  102.         adj[v].push_back({u, c});
  103.     }
  104.  
  105.     parent_node.resize(n);
  106.     for (int i = 0; i < n; ++i) parent_node[i] = i;
  107.  
  108.     state.assign(n, 0);
  109.     is_sink.assign(n, false);
  110.     sz.assign(n, 0);
  111.     expanded.assign(n, false);
  112.     comps.assign(n, nullptr);
  113.  
  114.     vector<int> active_stack;
  115.  
  116.     for (int i = 0; i < n; ++i) {
  117.         if (state[find_set(i)] == 0) {
  118.             int root = i;
  119.             comps[root] = new Component();
  120.             comps[root]->q.push_back(i);
  121.             comps[root]->nodes.push_back(i);
  122.             state[root] = 1;
  123.             active_stack.push_back(root);
  124.  
  125.             while (!active_stack.empty()) {
  126.                 int curr = active_stack.back();
  127.                 bool paused = false;
  128.  
  129.                 while (!comps[curr]->q.empty()) {
  130.                     int u = comps[curr]->q.back();
  131.                     comps[curr]->q.pop_back();
  132.  
  133.                     int root_u = find_set(u);
  134.                     if (root_u != curr) {
  135.                         if (state[root_u] == 0) {
  136.                             // Znaleziono nową, nieodwiedzoną składową
  137.                             comps[curr]->q.push_back(u); 
  138.  
  139.                             comps[u] = new Component();
  140.                             comps[u]->q.push_back(u);
  141.                             comps[u]->nodes.push_back(u);
  142.                             state[u] = 1;
  143.                             active_stack.push_back(u);
  144.                             paused = true;
  145.                             break;
  146.                         } else if (state[root_u] == 1) {
  147.                             // Znaleziono cykl aktywnych składowych
  148.                             comps[curr]->q.push_back(u); 
  149.  
  150.                             vector<int> cycle_comps;
  151.                             while (true) {
  152.                                 int top = active_stack.back();
  153.                                 active_stack.pop_back();
  154.                                 cycle_comps.push_back(top);
  155.                                 if (top == root_u) break;
  156.                             }
  157.                             int new_root = cycle_comps[0];
  158.                             for (size_t k = 1; k < cycle_comps.size(); ++k) {
  159.                                 new_root = merge_components(new_root, cycle_comps[k]);
  160.                             }
  161.                             active_stack.push_back(new_root);
  162.                             paused = true;
  163.                             break;
  164.                         } else if (state[root_u] == 2) {
  165.                             // Znaleziono dojście do przetworzonego grafu (ta składowa nie jest ujściem)
  166.                             state[curr] = 2;
  167.                             is_sink[curr] = false;
  168.                             active_stack.pop_back();
  169.                             delete comps[curr];
  170.                             comps[curr] = nullptr;
  171.                             paused = true;
  172.                             break;
  173.                         }
  174.                     } else {
  175.                         // Ekspansja własnego węzła
  176.                         if (!expanded[u]) {
  177.                             expanded[u] = true;
  178.                             int key = r[u];
  179.                             if (comps[curr]->keys.find(key) == comps[curr]->keys.end()) {
  180.                                 comps[curr]->keys.insert(key);
  181.                                 auto it = comps[curr]->blocked.find(key);
  182.                                 if (it != comps[curr]->blocked.end()) {
  183.                                     for (int nxt : it->second) comps[curr]->q.push_back(nxt);
  184.                                     comps[curr]->blocked.erase(it);
  185.                                 }
  186.                             }
  187.                             for (auto& edge : adj[u]) {
  188.                                 int v = edge.first;
  189.                                 int req_key = edge.second;
  190.                                 if (comps[curr]->keys.find(req_key) != comps[curr]->keys.end()) {
  191.                                     comps[curr]->q.push_back(v);
  192.                                 } else {
  193.                                     comps[curr]->blocked[req_key].push_back(v);
  194.                                 }
  195.                             }
  196.                         }
  197.                     }
  198.                 }
  199.  
  200.                 if (!paused) {
  201.                     // Składowa w całości eksplorowana (jest ujściem!)
  202.                     state[curr] = 2;
  203.                     is_sink[curr] = true;
  204.                     sz[curr] = comps[curr]->nodes.size();
  205.                     active_stack.pop_back();
  206.                     delete comps[curr];
  207.                     comps[curr] = nullptr;
  208.                 }
  209.             }
  210.         }
  211.     }
  212.  
  213.     // Znajdowanie najmniejszego rozmiaru ujścia
  214.     int min_p = 1e9;
  215.     for (int i = 0; i < n; ++i) {
  216.         int root = find_set(i);
  217.         if (is_sink[root]) {
  218.             min_p = min(min_p, sz[root]);
  219.         }
  220.     }
  221.  
  222.     // Wypisywanie wyniku zgodnie ze specyfikacją wejścia/wyjścia (n zer/jedynek)
  223.     for (int i = 0; i < n; ++i) {
  224.         int root = find_set(i);
  225.         if (is_sink[root] && sz[root] == min_p) {
  226.             cout << 1 << (i == n - 1 ? "" : " ");
  227.         } else {
  228.             cout << 0 << (i == n - 1 ? "" : " ");
  229.         }
  230.     }
  231.     cout << "\n";
  232.  
  233.     return 0;
  234. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4 5 
0 1 1 2 
0 1 0 
0 2 0 
1 2 1 
1 3 0 
3 1 2
stdout
copy 
0 1 1 0
https://ideone.com/9L5C3F
language:
C++14 (gcc 8.3)
created:
1 day 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!