結果

問題 No.529 帰省ラッシュ
ユーザー 👑 hos.lyrichos.lyric
提出日時 2019-06-07 13:00:58
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 1,145 ms / 4,500 ms
コード長 7,134 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 211,384 KB
実行使用メモリ 51,596 KB
最終ジャッジ日時 2024-06-22 01:37:05
合計ジャッジ時間 11,752 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 8 ms
6,940 KB
testcase_05 AC 7 ms
6,940 KB
testcase_06 AC 7 ms
6,944 KB
testcase_07 AC 7 ms
6,940 KB
testcase_08 AC 386 ms
30,692 KB
testcase_09 AC 384 ms
30,732 KB
testcase_10 AC 455 ms
35,144 KB
testcase_11 AC 468 ms
35,460 KB
testcase_12 AC 373 ms
32,540 KB
testcase_13 AC 724 ms
51,596 KB
testcase_14 AC 381 ms
33,744 KB
testcase_15 AC 1,134 ms
39,848 KB
testcase_16 AC 1,145 ms
38,788 KB
testcase_17 AC 1,035 ms
46,888 KB
testcase_18 AC 1,018 ms
47,724 KB
testcase_19 AC 1,019 ms
44,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
  BinaryHeap!(Array!int) que;
  Tuple!(int, int) mx;
  this(int id) {
    l = r = p = null;
    size = 1;
    this.id = id;
    que = BinaryHeap!(Array!int)();
    mx = tuple(-1, -1);
  }
  void update() {
    size = (l ? l.size : 0) + 1 + (r ? r.size : 0);
    mx = max(l ? l.mx : tuple(-1, -1), !que.empty ? tuple(que.front, id) : tuple(-1, -1), r ? r.mx : tuple(-1, -1));
  }
  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) {
    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);
  }
  */
  Tuple!(int, int) path(Tree u) {
    expose(); Tree v = u.expose(); splay(); v.splay();
    auto ret = tuple(-1, -1);
    if (v != this) {
      if (l) chmax(ret, l.mx);
      if (!que.empty) chmax(ret, tuple(que.front, id));
    }
    if (!v.que.empty) chmax(ret, tuple(v.que.front, v.id));
    if (v.r) chmax(ret, v.r.mx);
    return ret;
  }
}

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)%s>",
        u.l ? (dfs(u.l) ~ " ") : "",
        u.id, u.size, u.que, u.mx,
        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 root(int[] uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u]));
}
bool connect(int[] uf, int u, int v) {
  u = uf.root(u);
  v = uf.root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int N, M, Q;
int[] A, B;
int[] X, U, W, S, T;

int[][] graph;
int[] par, dis, low;
int zeit;

void dfs(int u, int p) {
  par[u] = p;
  dis[u] = low[u] = zeit++;
  foreach (v; graph[u]) {
    if (v != p) {
      if (dis[v] == -1) {
        dfs(v, u);
        chmin(low[u], low[v]);
      } else {
        chmin(low[u], dis[v]);
      }
    }
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      M = readInt();
      Q = readInt();
      A = new int[M];
      B = new int[M];
      foreach (i; 0 .. M) {
        A[i] = readInt() - 1;
        B[i] = readInt() - 1;
      }
      X = new int[Q];
      U = new int[Q];
      W = new int[Q];
      S = new int[Q];
      T = new int[Q];
      foreach (q; 0 .. Q) {
        X[q] = readInt();
        switch (X[q]) {
          case 1: {
            U[q] = readInt() - 1;
            W[q] = readInt();
          } break;
          case 2: {
            S[q] = readInt() - 1;
            T[q] = readInt() - 1;
          } break;
          default: assert(false);
        }
      }
      
      graph = new int[][N];
      foreach (i; 0 .. M) {
        graph[A[i]] ~= B[i];
        graph[B[i]] ~= A[i];
      }
      par = new int[N];
      dis = new int[N];
      low = new int[N];
      dis[] = -1;
      zeit = 0;
      dfs(0, -1);
      auto isBridge = new int[M];
      foreach (i; 0 .. M) {
        int u = A[i], v = B[i];
        if (dis[u] > dis[v]) {
          swap(u, v);
        }
        isBridge[i] = (u == par[v] && dis[v] <= low[v]);
      }
      debug {
        writeln("isBridge = ", isBridge);
      }
      
      auto uf = new int[N];
      uf[] = -1;
      foreach (i; 0 .. M) {
        if (!isBridge[i]) {
          uf.connect(A[i], B[i]);
        }
      }
      
      auto nodes = new Tree[N];
      foreach (u; 0 .. N) {
        if (uf[u] < 0) {
          nodes[u] = new Tree(u);
        }
      }
      foreach (i; 0 .. M) {
        if (isBridge[i]) {
          int u = A[i], v = B[i];
          if (par[u] == v) {
            swap(u, v);
          }
          nodes[uf.root(v)].link(nodes[uf.root(u)]);
        }
      }
      foreach (q; 0 .. Q) {
        switch (X[q]) {
          case 1: {
            int u = uf.root(U[q]);
            nodes[u].que.insert(W[q]);
            nodes[u].mx = !nodes[u].que.empty ? tuple(nodes[u].que.front, u) : tuple(-1, -1);
            nodes[u].expose;
          } break;
          case 2: {
            const res = nodes[uf.root(S[q])].path(nodes[uf.root(T[q])]);
            writeln(res[0]);
            if (res[1] != -1) {
              int u = res[1];
              nodes[u].que.removeFront;
              nodes[u].mx = !nodes[u].que.empty ? tuple(nodes[u].que.front, u) : tuple(-1, -1);
              nodes[u].expose;
            }
          } break;
          default: assert(false);
        }
      }
    }
  } catch (EOFException e) {
  }
}
0