2017.md

Potyczki Algorytmiczne 2017

Round 0

• Liczby drugie
• Kanapka
• Krążki 2

Liczby drugie (dru)

Kanapka (kan)

Krążki 2 (kra)

Round 1

• Permutacja [A]
• Skarbonka [B]

Permutacja [A] (per)

Skarbonka [B] (ska)

Round 2

• Iloczyn [A]
• Zapiekanki 2 [B]

Iloczyn [A] (ilo)

Zapiekanki 2 [B] (zap)

Round 3

• Mozaika [B]
• Praca domowa [A]

Mozaika [B] (moz)

Praca domowa [A] (pra)

Round 4

• Działka 2 [B]
• Skup akcji [A]

Działka 2 [B] (dzi)

Skup akcji [A] (sku)

Round 5

• Banany [B]
• Carcassonne [B]
• Giewont [A]
• Osady i warownie [A]

Banany [B] (ban)

题意：有一棵$n$个点的树，第$i$个点权为$z_i$，每条边有个费用$w$。一开始在$s=1$号点，有$q$个操作：

• $1\ i\ z_i$：修改点$i$的点权为$z_i$
• $2\ u\ v\ w$：修改$u$到$v$的边权为$w$。

每次操作后找到一个$t$，使得$z_t-\sum\limits_{e \in \text{Path}(s,t)} w(e)$最大，并把$s$改成$t$。如果有多个$t$，找标号最小那个。

$1 \le n, q \le 10^5, 1 \le z_i \le 10^{18}, 1 \le w \le 10^{12}$

题解：维护树分治结构即可。

Carcassonne [B] (car)

Giewont [A] (gie)

Osady i warownie [A] (osa)

Finals

• Galeria handlowa
• Przesył
• Sumowanie
• Klawiatura
• Trenerzy
• Wielokąt
• Machine learning
• Niebanalne podróże 2

Galeria handlowa (gal)

Przesył (prz)

Sumowanie (sum)

Klawiatura (kla)

Trenerzy (tre)

Wielokąt (wie)

Machine learning (mac)

Niebanalne podróże 2 (nie)