fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_N = 100005;
  9. const int MAX_V = 600005; // Rozmiar grafu: Drzewo przedziałowe (~262k) + Pomiary (200k)
  10.  
  11. int N, S_wells, M;
  12. int fixed_depth[MAX_N];
  13.  
  14. int S; // Rozmiar drzewa przedziałowego (potęga 2)
  15. vector<int> adj[MAX_V];
  16. int in_degree[MAX_V];
  17. long long dp[MAX_V];
  18.  
  19. // Funkcja dodająca krawędzie z przedziałów [A, B] do wierzchołka pomocniczego U
  20. void add_range_edges(int A, int B, int U) {
  21.     A += S - 1;
  22.     B += S - 1;
  23.     while (A <= B) {
  24.         if (A % 2 == 1) { // A to prawe dziecko, dodajemy całe i przechodzimy w prawo
  25.             adj[A].push_back(U);
  26.             in_degree[U]++;
  27.             A++;
  28.         }
  29.         if (B % 2 == 0) { // B to lewe dziecko, dodajemy całe i przechodzimy w lewo
  30.             adj[B].push_back(U);
  31.             in_degree[U]++;
  32.             B--;
  33.         }
  34.         A /= 2;
  35.         B /= 2;
  36.     }
  37. }
  38.  
  39. int main() {
  40.     // Optymalizacja operacji wejścia/wyjścia (niezbędne w tym zadaniu!)
  41.     ios_base::sync_with_stdio(false);
  42.     cin.tie(NULL);
  43.  
  44.     if (!(cin >> N >> S_wells >> M)) return 0;
  45.  
  46.     for (int i = 0; i < S_wells; ++i) {
  47.         int p, d;
  48.         cin >> p >> d;
  49.         fixed_depth[p] = d;
  50.     }
  51.  
  52.     // Wyznaczanie potęgi 2 pod rozmiar drzewa
  53.     S = 1;
  54.     while (S < N) S *= 2;
  55.  
  56.     // Budowanie szkieletu drzewa przedziałowego (krawędzie: dziecko -> rodzic)
  57.     for (int i = 1; i < S; ++i) {
  58.         adj[2 * i].push_back(i);
  59.         in_degree[i]++;
  60.         adj[2 * i + 1].push_back(i);
  61.         in_degree[i]++;
  62.     }
  63.  
  64.     // Odczytywanie pomiarów i budowanie zależności
  65.     for (int i = 0; i < M; ++i) {
  66.         int U = 2 * S + i; // Index sztucznego wierzchołka reprezentującego ten pomiar
  67.         int L, R, K;
  68.         cin >> L >> R >> K;
  69.         vector<int> X(K);
  70.         for (int j = 0; j < K; ++j) {
  71.             cin >> X[j];
  72.         }
  73.  
  74.         // 1. Zależności typu: Wszystko z wykluczeniem punktów X -> U
  75.         int curr = L;
  76.         for (int j = 0; j < K; ++j) {
  77.             int x = X[j];
  78.             if (curr <= x - 1) {
  79.                 add_range_edges(curr, x - 1, U);
  80.             }
  81.             curr = x + 1;
  82.         }
  83.         if (curr <= R) {
  84.             add_range_edges(curr, R, U);
  85.         }
  86.  
  87.         // 2. Zależności typu: U -> punkty X
  88.         for (int j = 0; j < K; ++j) {
  89.             int x = X[j];
  90.             int leaf_x = S + x - 1;
  91.             adj[U].push_back(leaf_x);
  92.             in_degree[leaf_x]++;
  93.         }
  94.     }
  95.  
  96.     // Ile wierzchołków grafu realnie używamy
  97.     int total_nodes = 2 * S + M - 1;
  98.     queue<int> Q;
  99.  
  100.     // Inicjalizacja pod sortowanie topologiczne
  101.     for (int i = 1; i <= total_nodes; ++i) {
  102.         if (in_degree[i] == 0) {
  103.             Q.push(i);
  104.         }
  105.         // Minimalna wartość dla danego miejsca
  106.         if (i >= S && i < S + N) {
  107.             int orig_idx = i - S + 1;
  108.             dp[i] = fixed_depth[orig_idx] ? fixed_depth[orig_idx] : 1;
  109.         } else {
  110.             dp[i] = 0; 
  111.         }
  112.     }
  113.  
  114.     int visited_count = 0;
  115.     vector<int> topo_order;
  116.     topo_order.reserve(total_nodes);
  117.  
  118.     // Sortowanie topologiczne (Algorytm Kahna)
  119.     while (!Q.empty()) {
  120.         int u = Q.front();
  121.         Q.pop();
  122.         visited_count++;
  123.         topo_order.push_back(u);
  124.  
  125.         for (int v : adj[u]) {
  126.             in_degree[v]--;
  127.             if (in_degree[v] == 0) {
  128.                 Q.push(v);
  129.             }
  130.         }
  131.     }
  132.  
  133.     // Wykryto cykl zależności = sytuacja niemożliwa
  134.     if (visited_count < total_nodes) {
  135.         cout << "NIE\n";
  136.         return 0;
  137.     }
  138.  
  139.     // Aktualizacja głębokości (najdłuższe ścieżki w DAG)
  140.     for (int u : topo_order) {
  141.         // Wszystkie krawędzie wychodzące z wierzchołków pomiarów wymuszają +1 do głębokości
  142.         int w = (u >= 2 * S) ? 1 : 0;
  143.         for (int v : adj[u]) {
  144.             dp[v] = max(dp[v], dp[u] + w);
  145.         }
  146.     }
  147.  
  148.     // Walidacja warunków krytycznych zadania
  149.     for (int i = 1; i <= N; ++i) {
  150.         int leaf = S + i - 1;
  151.         if (dp[leaf] > 1000000000LL) {
  152.             cout << "NIE\n";
  153.             return 0;
  154.         }
  155.         if (fixed_depth[i] != 0 && dp[leaf] > fixed_depth[i]) {
  156.             cout << "NIE\n";
  157.             return 0;
  158.         }
  159.     }
  160.  
  161.     // Wyjście
  162.     cout << "TAK\n";
  163.     for (int i = 1; i <= N; ++i) {
  164.         cout << dp[S + i - 1] << (i == N ? "" : " ");
  165.     }
  166.     cout << "\n";
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0.01s 20076KB
comments (?)
stdin
copy 
5 2 2
2 7
5 3
1 4 2 2 3
4 5 1 4
stdout
copy 
TAK
1 7 5 4 3
https://ideone.com/UovLT6
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!