#387056 (D) No.902 Query ζone

提出ソース

結果

問題	No.902 Query ζone
ユーザー	👑 hos.lyric
提出日時	2019-10-05 01:52:34
言語	D (dmd 2.106.1)
結果	WA
実行時間	-
コード長	7,064 bytes
コンパイル時間	1,437 ms
コンパイル使用メモリ	156,020 KB
実行使用メモリ	32,172 KB
最終ジャッジ日時	2023-09-04 02:58:31
合計ジャッジ時間	13,183 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 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	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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;
            }
            foreach (j; 0 .. k) {
              nodes[x[j]].expose;
            }
            long ans;
            foreach (j; 0 .. k) {
              auto v = nodes[x[j]].expose;
              ans -= get(v);
              ans += get(nodes[x[j]]);
            }
            writeln(ans);
          } break;
          default: assert(false);
        }
      }
    }
  } catch (EOFException e) {
  }
}

yukicoder

結果

テストケース

ソースコード