Diferențe pentru problema/capitala între reviziile #8 si #14

capitala

Capitala

== include(page="template/taskheader" task_id="capitala") ==

<!-- Fiecare simbol "(" adaugă 1em de padding la stânga -->
!((>problema/capitala?tree.png!

!>problema/capitala?tree.png!

Imperiul Roman se clatină sub atacurile barbarilor! Harta imperiului conține $N$ orașe și drumuri de legătură. Oricare drum poate fi parcurs într-o zi. Din eficiență, romanii au construit numărul minim necesar de drumuri pentru a putea călători între oricare două orașe. Orașele de la marginea imperiului se numesc avanposturi și au un singur drum de legătură.

h2. Restricții
* $3 ≤ N ≤ 100.000$

* Pentru 30% din teste, $3 ≤ N ≤ 5.000$

* Pentru 40% din teste, $3 ≤ N ≤ 5.000$

h2. Exemplu
table(example).
|_. capitala.in |_. capitala.out |
| 10

  6 4
  8 1
  1 5
  4 10
  9 6
  1 7
  3 7
  2 6
  6 3

6 4
8 1
1 5
4 10
9 6
1 7
3 7
2 6
6 3

| 2 2

  3 7

3 7

|
h3. Explicație

Orașul 3 are distanța 2 până la cele mai apropiate avanposturi (orașele 2 și 9). Orașul 7 are distanța 2 până la cele mai apropiate avanposturi (orașele 5 și 8). Toate celelalte orașe sunt la distanță 1 de cel mai apropiat avanpost sau sunt ele însele avanposturi.

Orașul 3 are distanța 2 până la cele mai apropiate avanposturi (orașele 2 și 9). Orașul 7 are distanța 2 până la cele mai apropiate avanposturi (orașele 5 și 8). Toate celelalte orașe sunt la distanță 1 de cel mai apropiat avanpost (1, 4, 6) sau sunt ele însele avanposturi (2, 5, 8, 9, 10).

== include(page="template/taskfooter" task_id="capitala") ==