結果

問題 No.1769 Don't Stop the Game
ユーザー 👑 hos.lyrichos.lyric
提出日時 2021-11-26 23:07:03
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 1,630 ms / 3,000 ms
コード長 6,801 bytes
コンパイル時間 2,234 ms
コンパイル使用メモリ 163,852 KB
実行使用メモリ 58,452 KB
最終ジャッジ日時 2023-09-04 15:08:56
合計ジャッジ時間 32,009 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 4 ms
4,380 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 4 ms
4,380 KB
testcase_06 AC 5 ms
4,380 KB
testcase_07 AC 5 ms
4,380 KB
testcase_08 AC 1,130 ms
29,784 KB
testcase_09 AC 702 ms
23,620 KB
testcase_10 AC 921 ms
28,576 KB
testcase_11 AC 763 ms
22,644 KB
testcase_12 AC 1,292 ms
35,752 KB
testcase_13 AC 1,268 ms
37,288 KB
testcase_14 AC 1,440 ms
37,264 KB
testcase_15 AC 1,630 ms
38,024 KB
testcase_16 AC 1,428 ms
39,796 KB
testcase_17 AC 1,266 ms
36,960 KB
testcase_18 AC 1,205 ms
37,288 KB
testcase_19 AC 1,175 ms
37,532 KB
testcase_20 AC 1,169 ms
38,800 KB
testcase_21 AC 1,194 ms
36,832 KB
testcase_22 AC 1,176 ms
40,600 KB
testcase_23 AC 754 ms
38,540 KB
testcase_24 AC 1,053 ms
36,760 KB
testcase_25 AC 449 ms
38,944 KB
testcase_26 AC 499 ms
36,424 KB
testcase_27 AC 825 ms
58,452 KB
testcase_28 AC 1,224 ms
57,108 KB
testcase_29 AC 1,072 ms
48,612 KB
testcase_30 AC 1,036 ms
48,356 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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) {
  }
}
0