結果
| 問題 | No.902 Query ζone |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2019-10-05 01:30:23 |
| 言語 | D (dmd 2.106.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,033 bytes |
| コンパイル時間 | 1,511 ms |
| コンパイル使用メモリ | 157,588 KB |
| 実行使用メモリ | 31,996 KB |
| 最終ジャッジ日時 | 2024-06-22 02:43:04 |
| 合計ジャッジ時間 | 11,198 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, 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)); }
class Tree {
Tree l, r, p;
int size;
int id;
// int[] val;
long val, sum;
// this(int id) {
this(int id, long val) {
l = r = p = null;
size = 1;
this.id = id;
// val = [id];
this.val = val;
sum = val;
}
void update() {
size = (l ? l.size : 0) + 1 + (r ? r.size : 0);
// val = (l ? l.val : []) ~ [id] ~ (r ? r.val : []);
sum = (l ? l.sum : 0) + val + (r ? r.sum : 0);
}
bool isRoot() const {
return (!p || (p.l != this && p.r != this));
}
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; }
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; u.r = this; u.update();
}
// parent of this := null
void cut() {
expose(); l.p = 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) {
long path(Tree u) {
expose(); Tree v = u.expose(); splay(); v.splay();
// auto pathT = (v == this) ? [] : ((l ? l.val : []) ~ [this.id]);
auto pathT = (v == this) ? 0 : ((l ? l.sum : 0) + this.val);
auto pathU = v.val + (v.r ? v.r.sum : 0);
// return tuple(pathT, pathU);
return 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>",
return format("<%s%s(%s, %s, %s)%s>",
u.l ? (dfs(u.l) ~ " ") : "",
// u.id, u.size, u.val,
u.id, u.size, u.val, u.sum,
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[] U, V;
long[] W;
int[][] G;
int[] par;
void dfs(int u, int p) {
par[u] = p;
foreach (i; G[u]) {
const v = U[i] ^ V[i] ^ u;
if (v != p) {
dfs(v, u);
}
}
}
void main() {
try {
for (; ; ) {
N = readInt();
U = new int[N - 1];
V = new int[N - 1];
W = new long[N - 1];
foreach (i; 0 .. N - 1) {
U[i] = readInt();
V[i] = readInt();
W[i] = readLong();
}
G = new int[][N];
foreach (i; 0 .. N - 1) {
G[U[i]] ~= i;
G[V[i]] ~= i;
}
par = new int[N];
dfs(0, -1);
auto vals = new long[N];
foreach (i; 0 .. N - 1) {
int u = U[i], v = V[i];
if (par[u] == v) {
swap(u, v);
}
vals[v] = W[i];
}
debug {
writeln("par = ", par);
writeln("vals = ", vals);
}
auto nodes = new Tree[N];
foreach (u; 0 .. N) {
nodes[u] = new Tree(u, vals[u]);
}
foreach (u; 0 .. N) {
if (par[u] != -1) {
nodes[u].link(nodes[par[u]]);
}
}
debug {
nodes.print;
}
const numQueries = readInt();
foreach (queryId; 0 .. numQueries) {
debug {
writeln("par = ", par);
}
switch (readInt()) {
case 1: {
const u = readInt();
const v = readInt();
const w = readInt();
const x = readLong();
debug {
writeln("change ", u, " - ", v, " - ", w);
}
if (par[u] == v) {
// toptree ga nainode uso link
int[] ys;
for (int y = w; y != u; y = par[y]) {
ys ~= y;
}
debug {
writeln("ys = ", ys);
}
nodes[u].cut;
foreach_reverse (y; ys) {
const p = par[y];
nodes[y].cut;
nodes[p].val = nodes[p].sum = nodes[y].val;
nodes[p].link(nodes[y]);
par[p] = y;
}
nodes[w].val = nodes[w].sum = x;
nodes[w].link(nodes[v]);
par[w] = v;
} else {
nodes[v].cut;
nodes[v].val = nodes[v].sum = x;
nodes[v].link(nodes[w]);
par[v] = w;
}
debug {
nodes.print;
}
} break;
case 2: {
const k = readInt();
auto x = new int[k];
foreach (j; 0 .. k) {
x[j] = readInt();
}
debug {
writeln("query x = ", x);
}
long get(Tree u) {
u.splay;
return (u.l ? u.l.sum : 0) + u.val;
}
nodes[x[0]].expose;
long ans = get(nodes[x[0]]);
foreach (j; 1 .. k) {
auto v = nodes[x[j]].expose;
ans -= get(v);
ans += get(nodes[x[j]]);
}
writeln(ans);
} break;
default: assert(false);
}
}
}
} catch (EOFException e) {
}
}