BZOJ 2125: 最短路

题解

圆方树

const int N = int(2e4) + 9, LV = 15;

int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;

inline int move_up(int x, int t){
for (int lv=0;t;++lv,t&gt;&gt;=1)
if (t&amp;1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}
void getLCA(int x, int y, int &amp;a, int &amp;b, int &amp;z) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
a = x; b = y; z = fa[0][x];
}

void add_edge(int u, int v, LL w) {
}

#define v it-&gt;fi
#define w it-&gt;se
void tarjan(int u = 1, int p = -1) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
ECH(it, adj[u]) if (v != p) {
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
} else if (dfn[v] &lt; dfn[u]) { // find circle
checkMin(low[u], dfn[v]);
add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
for (int i=top;sta[i]!=v;--i) {
int d = D[sta[i]]-D[v];
}
}
}
--top;
}
#define p fa[0][u]
void dfs(int u = 1) {
dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
dfs(v);
}
}
#undef p
#undef w
#undef v

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

int Q, m; RD(n, m, Q);

DO(m) {
int x, y, w; RD(x, y, w);
}

nn = n; tarjan(); dfs();

DO(Q) {
int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

//cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;

if (z &lt;= n) { // round one ...
OT(DD[x]+DD[y]-DD[z]*2);
} else { // square one ...
int d = abs(D[a]-D[b]);
OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
}
}
}


动态仙人掌

https://www.luogu.com.cn/record/31868182

论自杀

。后来我还找兔子认真的讨论了“自杀”这件事情。。。我当时只是觉得，如果真的要“自杀”的话，应该怎么做都会成功吧。。最简单的方法可能是，找个高楼大厦，忘记一切，跳下去就好。。。而且在都市圈的话，卧轨应该也是很多人的一个选择。。不过兔子说，那样会麻烦到其他人。。打扫起来很不方便，烧炭的话，如果失败会变成植物人。。。（所以果然还是“静脉注射氯化钡”最好？。。。）。。

分类

– 主动型自杀，为达成个人因素以外的目的而进行的自杀。例如，自杀攻击是为达到某种目的而自杀。（E.g. 三岛由纪夫）
– 被动型自杀，仅个人因素导致的自杀。比如逃离性自杀，例如社会压力而产生心理疾病、药物、醉酒、物质滥用等，是外因导致其自杀。（E.g. 阿兰图灵）

– 安乐死：个体以借助他人帮助的形式来完成自己的自杀。
– 谋杀自杀：一个人用谋杀的方式，让另一个人或几个人在他本人之前或同时死去。
– 相约自杀：两个或两个以上的个体之间立下协定，通常是因个人原因，同时或先后自杀。
– 集体自杀：集体自杀指一群人为了同一目的而自杀或互相杀害，而这通常与真实或意识到的迫害有关。（代表作，乱步奇谭）

主动型自杀

• 自杀式袭击：牺牲自己以完成攻击目的。如神风特攻队、恐怖攻击中的自杀炸弹客。
• 政治目的性自杀：为传达某种理念而自杀，例如死谏、殉情或以死明志，例如在某重要地标自焚。此类自杀亦常见要求他人协助完成者。如2019年自杀的香港反对修订逃犯条例示威者、郑南榕。

被动型自杀

• 胁迫性自杀：为了控制他人（罪恶感、恐惧）而自杀。因认为自己遭到某人恶意待遇（因动机来自感受到他人恶意，故列为被动型），而以死的方式作为报复手段。某些地方文化认为人死后产生的鬼可代为复仇，亦属这一类。
• 责任性自杀：为了显示责任心而自杀，如早期日本在战败时的切腹自杀（因具备文化因素，亦含主动性成分）。在现代，此类自杀常见于强迫性格倾向者。（E.g. 如最近负责日本武汉撤侨的首相官邸官员）
• 逃离性自杀：为了躲避某种事物（如恶疾、痛苦、恐慌、空虚等感受），或是被某事逼迫（如被逼债、畏罪、政权垮台），因而自杀。（大部分情况）

方式

“还有什么比创作出来的故事更真实的呢？”
—— 【剩余榨值023】在巨大的 shock 后，我们所思考的、所做的一切都将与此有关 34:00

坠楼

梦日记

。。自杀自然是十分诱人的… 所有描绘自杀的作品里。。最令人印象深刻的自然还是《梦日记》。在梦中辛苦游历收集了所有十二扇门的世界。最后的最后。。居然是选择结束了自己的生命。。。留给玩家无限多的想象空间。。。

自刎

霸王别姬

“吾闻汉购我头千金，邑万户，吾为若德。”
—— 《史记 项羽本纪》

—— 李清照《夏日绝句》

“汉兵已略地，四面楚歌声。大王意气尽，贱妾何聊生！”

“我们演一个剧，第一要自己懂得这个剧的意义，第二要明白观众对于这个戏的感情……还有人以为戏剧是用来开心取乐的，以为是玩意儿，其实不然”，“一个戏总有它的意义，算起总账来，就是一切戏剧都有提高人类生活目标的意义”

TBD

TBD

沉江

“俺史可法亡国罪臣，那容的冠裳而去。”
“你看茫茫世界，留着俺史可法何处安放。累死英雄，到此日看江山换主，无可留恋。”

。。。

—— 小岛 みなこ, [Jul 10, 2020 at 7:25:44 PM]

生死观

“人死之后，葬在地下，占得多少土地？”

“坟中安葬着丢番图。上帝给予的童年占六分之一，又过十二分之一，两颊长胡，再过七分之一，点燃起结婚的蜡烛。五年之后天赐贵子，可怜迟到的宁馨儿，享年仅及其父之半，便进入冰冷的墓。悲伤只有用数论的研究去弥补，又过四年，他也走完了人生的旅途。”

（类似的还有最近的 “Flight recorder inventor: Do Not Open”

TBD

题解

—— 官方题解

虚树

http://uoj.ac/submission/387435

虚仙人掌 (a.k.a. 圆方树)

void add_edge(int x, int y) {
if (x &gt; G.n &amp;&amp; x != C.fa[0][y]) { // 如果是从方点连出去，并且 y 不是连出去的那个孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
x = z;
}
}


http://uoj.ac/submission/387655

On Remote and Hiring

startup
gitlab

Don’t Trust, Always Verify