結果
| 問題 |
No.1769 Don't Stop the Game
|
| コンテスト | |
| ユーザー |
 hos.lyric
|
| 提出日時 | 2021-11-26 23:07:03 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 1,193 ms / 3,000 ms |
| コード長 | 6,801 bytes |
| コンパイル時間 | 1,822 ms |
| コンパイル使用メモリ | 168,056 KB |
| 実行使用メモリ | 58,600 KB |
| 最終ジャッジ日時 | 2024-06-22 13:30:06 |
| 合計ジャッジ時間 | 24,468 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
// Link-Cut Tree
// Modify val and update to the data needed
class Tree {
Tree l, r, p;
int size;
int id;
// int[] val;
int val;
this(int id) {
l = r = p = null;
size = 1;
this.id = id;
// val = [id];
val = 1;
}
void update() {
size = (l ? l.size : 0) + 1 + (r ? r.size : 0);
// val = (l ? l.val : []) ~ [id] ~ (r ? r.val : []);
// val = (l ? l.val : 0) + 1 + (r ? r.val : 0) + sub;
}
bool isRoot() const {
return (!p || (p.l != this && p.r != this));
}
// !
void change(Tree pp) {
if (p) p.val -= val;
p = pp;
if (p) p.val += val;
}
void rotate() {
// if (p.l == this) { if (r) { r.p = p; } p.l = r; r = p; }
// else if (p.r == this) { if (l) { l.p = p; } p.r = l; l = p; }
if (p.l == this) { const sub = r ? r.val : 0; if (r) { r.p = p; } p.l = r; r = p; swap(val, p.val); p.val = val - p.val + sub; }
else if (p.r == this) { const sub = l ? l.val : 0; if (l) { l.p = p; } p.r = l; l = p; swap(val, p.val); p.val = val - p.val + sub; }
Tree pp = p.p;
if (pp) {
if (pp.l == p) pp.l = this;
else if (pp.r == p) pp.r = this;
}
p.update(); p.p = this; p = pp;
}
void splay() {
for (; !isRoot(); rotate()) {
if (!p.isRoot()) ((p.l == this) == (p.p.l == p)) ? p.rotate() : rotate();
}
update();
}
// Make the path from v to the root solid
// Return the node where it entered the last solid path
Tree expose() {
Tree u = this, v = null;
for (; u; u = u.p) { u.splay(); u.r = v; u.update(); v = u; }
splay();
return v;
}
// parent of this := u
void link(Tree u) {
expose(); u.expose(); /*p = u;*/change(u); u.r = this; u.update();
}
// parent of this := null
void cut() {
expose(); /*l.p = null;*/l.change(null); l = null; update();
}
// the root of the tree this belongs
Tree root() {
expose();
for (Tree u = this; ; u = u.l) if (!u.l) { u.splay(); return u; }
}
// LCA of this and u
// Assume this.root == u.root
Tree lca(Tree u) {
expose(); return u.expose();
}
/*
// ([child of LCA, ..., this], [LCA, ..., u])
// Assume this.root == u.root
import std.typecons : Tuple, tuple;
Tuple!(int[], int[]) path(Tree u) {
expose(); Tree v = u.expose(); splay(); v.splay();
auto pathT = (v == this) ? [] : ((l ? l.val : []) ~ [this.id]);
auto pathU = [v.id] ~ (v.r ? v.r.val : []);
return tuple(pathT, pathU);
}
*/
}
void print(in Tree[] nodes) {
import std.stdio : write, writeln;
import std.string : format;
string dfs(in Tree u) {
return format("<%s%s(%s, %s)%s>",
u.l ? (dfs(u.l) ~ " ") : "",
u.id, u.size, u.val,
u.r ? (" " ~ dfs(u.r)) : "");
}
foreach (u; nodes) {
if (u.isRoot()) {
write("| ");
if (u.p) write(u.p.id, " ");
write("<- ", u.id, ": ");
writeln(dfs(u));
}
}
}
int N;
int[] A, B;
long[] C;
int[][] G;
int[] par;
long[] dist;
void dfs(int u, int p) {
par[u] = p;
foreach (i; G[u]) {
const v = A[i] ^ B[i] ^ u;
if (v != p) {
dist[v] = dist[u] ^ C[i];
dfs(v, u);
}
}
}
void main() {
try {
for (; ; ) {
N = readInt();
A = new int[N - 1];
B = new int[N - 1];
C = new long[N - 1];
foreach (i; 0 .. N - 1) {
A[i] = readInt() - 1;
B[i] = readInt() - 1;
C[i] = readLong();
}
G = new int[][N];
foreach (i; 0 .. N - 1) {
G[A[i]] ~= i;
G[B[i]] ~= i;
}
par = new int[N];
dist = new long[N];
dfs(0, -1);
debug {
writeln("par = ", par);
writeln("dist = ", dist);
}
auto nodes = new Tree[N];
foreach (u; 0 .. N) {
nodes[u] = new Tree(u);
}
foreach (u; 0 .. N) if (~par[u]) {
nodes[u].link(nodes[par[u]]);
}
auto del = new bool[N];
void add(int u) {
del[u] = false;
foreach (i; G[u]) {
const v = A[i] ^ B[i] ^ u;
if (v != par[u]) {
if (!del[v]) {
nodes[v].link(nodes[u]);
}
}
}
if (~par[u]) {
if (!del[par[u]]) {
nodes[u].link(nodes[par[u]]);
}
}
}
void rem(int u) {
del[u] = true;
foreach (i; G[u]) {
const v = A[i] ^ B[i] ^ u;
if (v != par[u]) {
if (!del[v]) {
nodes[v].cut;
}
}
}
if (~par[u]) {
if (!del[par[u]]) {
nodes[u].cut;
}
}
}
alias Entry = Tuple!(long, "d", int, "u");
auto es = new Entry[N];
foreach (u; 0 .. N) {
es[u] = Entry(dist[u], u);
}
es.sort;
auto anss = new long[N];
for (int j = 0, k; j < N; j = k) {
for (k = j; k < N && es[j].d == es[k].d; ++k) {}
debug {
writeln(es[j .. k]);
}
foreach (e; es[j .. k]) {
const u = e.u;
rem(u);
}
foreach (e; es[j .. k]) {
const u = e.u;
add(u);
const r = nodes[u].root.id;
nodes[r].expose;
debug {
writeln("u = ", u, ", r = ", r);
nodes.print;
}
anss[u] = nodes[r].val - 1;
rem(u);
}
foreach (e; es[j .. k]) {
const u = e.u;
add(u);
}
}
debug {
writeln("anss = ", anss);
}
const ans = anss.sum;
writeln(ans);
}
} catch (EOFException e) {
}
}