#537745 (D) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	👑 hos.lyric
提出日時	2020-08-22 15:19:21
言語	D (dmd 2.106.1)
結果	WA
実行時間	-
コード長	6,266 bytes
コンパイル時間	2,105 ms
コンパイル使用メモリ	154,916 KB
実行使用メモリ	20,248 KB
最終ジャッジ日時	2023-09-04 09:11:36
合計ジャッジ時間	17,499 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	2 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	1 ms 4,376 KB
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	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	AC	2 ms 4,376 KB
testcase_42	AC	2 ms 4,376 KB

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

ソースコード

raw source code

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;
  long here, num, sum;
  this(int id) {
    l = r = p = null;
    size = 1;
    this.id = id;
    // val = [id];
    num = here;
    sum = 0;
  }
  void update() {
    size = (l ? l.size : 0) + 1 + (r ? r.size : 0);
    // val = (l ? l.val : []) ~ [id] ~ (r ? r.val : []);
  }
  
  // ?
  void changeP(Tree u) {
    debug {
      writefln("%s.changeP %s -> %s", id, p ? p.id.to!string : "null", u ? u.id.to!string : "null");
    }
    if (p) {
      p.num -= num;
      p.sum -= (num + sum);
    }
    p = u;
    if (u) {
      u.num += num;
      u.sum += (num + sum);
    }
  }
  
  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; }
         if (p.l == this) { if (r) { r.changeP(p); } p.l = r; r = p; }
    // else if (p.r == this) { if (l) { l.p = p; } p.r = l; l = p; }
    else if (p.r == this) { if (l) { l.changeP(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;
    auto q = p;
    p.update(); changeP(pp); q.changeP(this);
  }
  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();
    expose(); u.expose(); changeP(u); u.r = this; u.update();
  }

  // parent of this := null
  void cut() {
    // expose(); l.p = null; l = null; update();
    expose(); l.changeP(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>",
    return format("<%s%s(%s, %s, %s,%s)%s>",
        u.l ? (dfs(u.l) ~ " ") : "",
        // u.id, u.size, u.val,
        u.id, u.size, u.here, u.num, 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));
    }
  }
}


void main() {
  try {
    for (; ; ) {
      const N = readInt();
      const K = readInt();
      const Q = readInt();
      auto C = new int[K];
      foreach (k; 0 .. K) {
        C[k] = readInt() - 1;
      }
      auto A = new int[N - 1];
      auto B = new int[N - 1];
      foreach (i; 0 .. N - 1) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      auto typ = new int[Q];
      auto P = new int[Q];
      auto D = new int[Q];
      auto E = new int[Q];
      foreach (q; 0 .. Q) {
        typ[q] = readInt();
        switch (typ[q]) {
          case 1: {
            P[q] = readInt() - 1;
            D[q] = readInt() - 1;
          } break;
          case 2: {
            E[q] = readInt() - 1;
          } break;
          default: assert(false);
        }
      }
      
      auto nodes = new Tree[N];
      foreach (u; 0 .. N) {
        nodes[u] = new Tree(u);
      }
      foreach (k; 0 .. K) {
        nodes[C[k]].here += 1;
        nodes[C[k]].num += 1;
      }
      debug {
        nodes.print;
        writeln("----");
      }
      foreach (i; 0 .. N - 1) {
        nodes[A[i]].link(nodes[B[i]]);
        debug {
          nodes.print;
          writeln("----");
        }
      }
      
      auto cs = C.dup;
      foreach (q; 0 .. Q) {
        switch (typ[q]) {
          case 1: {
            const k = P[q];
            nodes[cs[k]].expose;
            nodes[cs[k]].here -= 1;
            nodes[cs[k]].num -= 1;
            cs[k] = D[q];
            nodes[cs[k]].expose;
            nodes[cs[k]].here += 1;
            nodes[cs[k]].num += 1;
          } break;
          case 2: {
            nodes[E[q]].expose;
            writeln(nodes[E[q]].sum);
          } break;
          default: assert(false);
        }
        debug {
          nodes.print;
          writeln("----");
        }
      }
    }
  } catch (EOFException e) {
  }
}

yukicoder

結果

テストケース

ソースコード