fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. import java.util.Scanner;
  5.  
  6. public class Main {
  7.     static final int NMAX = 100001;
  8.     static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>> (NMAX);
  9.     static ArrayList<Integer> killed = new ArrayList<Integer> (NMAX);
  10.     static ArrayList<Boolean> used = new ArrayList<Boolean> (NMAX);
  11.     static ArrayList<Integer> dist = new ArrayList<Integer> (NMAX);
  12.     static int ans = 0;
  13.  
  14.     public static void kills(int v, int p)
  15.     {
  16.         if (v == p) kills(tree.get(v).get(0), v);
  17.         if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) kills(to, v);
  18.         if (tree.get(v).size() >= 3) killed.set(v, killed.get(v) + 1);
  19.         return;
  20.     }
  21.  
  22.     public static void goup(int v, int p)
  23.     {
  24.         if (v == p)
  25.         {
  26.             for (Integer to : tree.get(v)) if (dist.get(to) < dist.get(v)) goup(to, v);
  27.             killed.set(v, 0);
  28.             return;
  29.         }
  30.         if (tree.get(v).size() == 2) for (Integer to : tree.get(v)) if (to != p) goup(to, v);
  31.         if (tree.get(v).size() >= 3)
  32.         {
  33.             killed.set(v, killed.get(v) + 1);
  34.             return;
  35.         }
  36.     }
  37.  
  38.     public static void main(String[] args) {
  39.         Scanner in = new Scanner(System.in);
  40.         for (int i=0;i<NMAX; i++)
  41.         {
  42.             tree.add(new ArrayList<Integer>());
  43.             dist.add(0);
  44.             used.add(false);
  45.             killed.add(0);
  46.         }
  47.         int n,v;
  48.         n = in.nextInt();
  49.         if (n <= 5) {System.out.print(1); return;} // Частный случай
  50.         tree.get(1).add(0); // Корень тоже должен быть "развилкой"
  51.         ArrayList<Integer> leaves = new ArrayList<Integer> ();
  52.         for (int i = 1; i < n; i++)
  53.         {
  54.             v = in.nextInt();
  55.             tree.get(v).add(i+1);
  56.             tree.get(i+1).add(v); //Заполнение графа в том виде, в котором его дают
  57.         }
  58.  
  59.         for (int i = 1; i <= n; i++)
  60.         {
  61.             if (tree.get(i).size() == 1 || (i == 1 && tree.get(i).size() == 2)) leaves.add(i); //Запоминаем все листья
  62.         }
  63.  
  64.         LinkedList<Integer> q = new LinkedList<>(); dist.set(1, 0);
  65.         q.offer(1); used.set(1, true);
  66.         while (!q.isEmpty())
  67.         {
  68.             int qv = q.poll();
  69.             used.set(qv, true);
  70.             for (Integer to : tree.get(qv))                //BFS заполняющий вектор dist
  71.             {
  72.                 if (!used.get(to))
  73.                 {
  74.                     q.offer(to);
  75.                     dist.set(to, dist.get(qv)+1);
  76.                 }
  77.             }
  78.         }
  79.  
  80.         for (Integer l : leaves)
  81.         {
  82.             kills(l, l);        // Первый этап - запросы от каждого листа
  83.         }
  84.  
  85.         int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = Math.max(maxdist, dist.get(i)); // Определение максимального "уровня" дерева
  86.         int wentup = 1;
  87.         while (wentup != 0)
  88.         {
  89.             wentup = 0;
  90.             for (int l = maxdist; l > 0; l--)
  91.             {
  92.                 for (int i = 2; i <= n; i++)
  93.                 {
  94.                     if (killed.get(i) == 1 && dist.get(i) == l)
  95.                     {
  96.                         goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
  97.                         wentup++;
  98.                     }
  99.                 }
  100.             }
  101.         }
  102.         for (int i = 1; i <= n; i++) if (killed.get(i) >= 2) ans++; //Финальный подсчет "отравленных" развилок
  103.         System.out.print(ans);
  104.     }
  105. }
Success #stdin #stdout 0.12s 42136KB
comments (?)
stdin
copy 
16
1 2 3 4 5 3 7 1 9 9 11 11 13 13 15
stdout
copy 
3
https://ideone.com/eW82L0
e-olymp 9414. Убить всех термитов
language:
Java (HotSpot 12)
created:
4 years 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!