AtCoder Regular Contest 039

Submission #818954

Source codeソースコード

#include <algorithm>
#include <utility>
#include <vector>

using Graph = std::vector<std::vector<int>>;
using Edge = std::pair<int, int>;

class BridgeHelper {
  const Graph& graph;
  std::vector<int> ord, low;
  int k = 0;

public:
  std::vector<Edge> bridges;

  BridgeHelper(const Graph& graph) : graph(graph), ord(graph.size(), -1), low(graph.size()) {
    for (int u = 0; u < graph.size(); ++u) {
      if (ord[u] >= 0) continue;
      dfs(u);
    }
  }
  bool is_bridge(int u, int v) const {
    if (ord[u] > ord[v]) std::swap(u, v);
    return ord[u] < low[v];
  }

private:
  void dfs(int u, int p = -1) {
    ord[u] = low[u] = k;
    ++k;
    for (int v : graph[u]) {
      if (v == p) continue;
      if (ord[v] >= 0) {
        low[u] = std::min(low[u], ord[v]);
      } else {
        dfs(v, u);
        low[u] = std::min(low[u], low[v]);
      }
      if (is_bridge(u, v)) bridges.emplace_back(u, v);
    }
  }
};

struct BICC {
  std::vector<std::vector<int>> comps;
  std::vector<int> belongs;
  const BridgeHelper bridge_helper;

private:
  const Graph& graph;

public:
  BICC(const Graph& graph) : graph(graph), bridge_helper(graph), belongs(graph.size(), -1) {
    for (const auto& bridge : bridge_helper.bridges) {
      add_component(bridge.first);
      add_component(bridge.second);
    }
    add_component(0);
  }
  Graph to_tree() const {
    Graph tree(comps.size());
    for (const auto& bridge : bridge_helper.bridges) {
      int u = belongs[bridge.first], v = belongs[bridge.second];
      tree[u].emplace_back(v);
      tree[v].emplace_back(u);
    }
    return tree;
  }

private:
  void fill_component(int c, int u) {
    comps[c].emplace_back(u);
    belongs[u] = c;
    for (int v : graph[u]) {
      if (belongs[v] >= 0) continue;
      if (bridge_helper.is_bridge(u, v)) continue;
      fill_component(c, v);
    }
  }
  void add_component(int u) {
    if (belongs[u] >= 0) return;
    comps.emplace_back();
    fill_component(comps.size() - 1, u);
  }
};

constexpr int roundup_log2(int x, int a = 1, int k = 0) {
  return a < x ? roundup_log2(x, a + a, k + 1) : std::max(k, 1);
}

struct LCA {
private:
  const Graph& tree;
  const int root;
  std::vector<int> depth;
  std::vector<std::vector<int>> parent;

public:
  LCA(const Graph& tree, int root)
      : tree(tree), root(root), depth(tree.size()),
        parent(roundup_log2(tree.size()), std::vector<int>(tree.size())) {
    build(root);
    for (int k = 0; k + 1 < parent.size(); ++k) {
      for (int u = 0; u < tree.size(); ++u) {
        if (parent[k][u] < 0) {
          parent[k + 1][u] = -1;
        } else {
          parent[k + 1][u] = parent[k][parent[k][u]];
        }
      }
    }
  }
  int query(int u, int v) const {
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int k = 0; k < parent.size(); ++k) {
      if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
    }
    if (u == v) return u;
    for (int k = parent.size() - 1; k >= 0; --k) {
      if (parent[k][u] == parent[k][v]) continue;
      u = parent[k][u];
      v = parent[k][v];
    }
    return parent[0][u];
  }
  int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[query(u, v)]; }

private:
  void build(int u, int p = -1, int d = 0) {
    parent[0][u] = p;
    depth[u] = d;
    for (int v : tree[u]) {
      if (v == p) continue;
      build(v, u, d + 1);
    }
  }
};

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}

int main() {
  int N = in(), M = in();
  Graph G(N);
  rep(i, M) {
    int u = in() - 1, v = in() - 1;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  BICC bicc(G);
  Graph tree = bicc.to_tree();
  LCA lca(tree, 0);
  int Q = in();
  rep(i, Q) {
    int A = in() - 1, B = in() - 1, C = in() - 1;
    int X = bicc.belongs[A], Y = bicc.belongs[B], Z = bicc.belongs[C];
    if (lca.dist(X, Z) == lca.dist(X, Y) + lca.dist(Y, Z)) {
      puts("OK");
    } else {
      puts("NG");
    }
  }
  return 0;
}

Submission

Task問題 D - 旅行会社高橋君
User nameユーザ名 orisano
Created time投稿日時
Language言語 C++11 (GCC 4.9.2)
Status状態 AC
Score得点 100
Source lengthソースコード長 4221 Byte
File nameファイル名
Exec time実行時間 398 ms
Memory usageメモリ使用量 30576 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int in()’:
./Main.cpp:147:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_0.txt,sample_1.txt,sample_2.txt
All 100 / 100 bigcycleandsub_0.txt,bigcycleandsub_1.txt,cluster_0.txt,cluster_1.txt,cluster_2.txt,cluster_3.txt,cluster_4.txt,cycleline_0.txt,cycleline_1.txt,cycleline_2.txt,cycleline_3.txt,cycleline_4.txt,cycletree_0.txt,cycletree_1.txt,cycletree_2.txt,cycletree_3.txt,cycletree_4.txt,large_0.txt,large_1.txt,large_2.txt,line_0.txt,line_1.txt,lineandsub_0.txt,lineandsub_1.txt,lineandsub_2.txt,maxrand_0.txt,maxrand_1.txt,maxrand_2.txt,maxrandandsub_0.txt,maxrandandsub_1.txt,maxrandandsub_2.txt,maxrandandsub_3.txt,maxrandandsub_4.txt,med_0.txt,med_1.txt,med_2.txt,med_3.txt,med_4.txt,med_5.txt,med_6.txt,med_7.txt,med_8.txt,med_9.txt,perfect_0.txt,perfect_1.txt,perfect_2.txt,small_0.txt,small_1.txt,small_2.txt,small_3.txt,small_4.txt,small_5.txt,small_6.txt,small_7.txt,small_8.txt,small_9.txt,star_0.txt,star_1.txt,star_2.txt,tencluster_0.txt,tencluster_1.txt,tencluster_2.txt,tencluster_3.txt,tencluster_4.txt,tree_0.txt,tree_1.txt,tree_2.txt,verysmall_0.txt,verysmall_1.txt,verysmall_2.txt,verysmall_3.txt,verysmall_4.txt,verysmall_5.txt,verysmall_6.txt,verysmall_7.txt,verysmall_8.txt,verysmall_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
bigcycleandsub_0.txt AC 359 ms 13428 KB
bigcycleandsub_1.txt AC 319 ms 13436 KB
cluster_0.txt AC 243 ms 9732 KB
cluster_1.txt AC 242 ms 9860 KB
cluster_2.txt AC 239 ms 9732 KB
cluster_3.txt AC 240 ms 9864 KB
cluster_4.txt AC 238 ms 9776 KB
cycleline_0.txt AC 235 ms 9616 KB
cycleline_1.txt AC 237 ms 9640 KB
cycleline_2.txt AC 236 ms 9676 KB
cycleline_3.txt AC 238 ms 9668 KB
cycleline_4.txt AC 235 ms 9672 KB
cycletree_0.txt AC 222 ms 9412 KB
cycletree_1.txt AC 237 ms 9480 KB
cycletree_2.txt AC 226 ms 9512 KB
cycletree_3.txt AC 225 ms 9476 KB
cycletree_4.txt AC 222 ms 9488 KB
large_0.txt AC 221 ms 11312 KB
large_1.txt AC 64 ms 2684 KB
large_2.txt AC 164 ms 10760 KB
line_0.txt AC 309 ms 30576 KB
line_1.txt AC 218 ms 29872 KB
lineandsub_0.txt AC 381 ms 29560 KB
lineandsub_1.txt AC 398 ms 30188 KB
lineandsub_2.txt AC 383 ms 29812 KB
maxrand_0.txt AC 240 ms 13440 KB
maxrand_1.txt AC 239 ms 13356 KB
maxrand_2.txt AC 240 ms 13320 KB
maxrandandsub_0.txt AC 261 ms 14080 KB
maxrandandsub_1.txt AC 260 ms 14140 KB
maxrandandsub_2.txt AC 257 ms 14080 KB
maxrandandsub_3.txt AC 254 ms 14080 KB
maxrandandsub_4.txt AC 265 ms 14124 KB
med_0.txt AC 34 ms 1216 KB
med_1.txt AC 30 ms 1128 KB
med_2.txt AC 30 ms 1224 KB
med_3.txt AC 31 ms 1212 KB
med_4.txt AC 36 ms 1328 KB
med_5.txt AC 31 ms 1260 KB
med_6.txt AC 31 ms 1324 KB
med_7.txt AC 33 ms 1308 KB
med_8.txt AC 32 ms 1216 KB
med_9.txt AC 31 ms 1192 KB
perfect_0.txt AC 86 ms 2096 KB
perfect_1.txt AC 68 ms 2188 KB
perfect_2.txt AC 85 ms 2096 KB
sample_0.txt AC 29 ms 1220 KB
sample_1.txt AC 32 ms 1284 KB
sample_2.txt AC 32 ms 1288 KB
small_0.txt AC 33 ms 1284 KB
small_1.txt AC 31 ms 1156 KB
small_2.txt AC 30 ms 1276 KB
small_3.txt AC 30 ms 1280 KB
small_4.txt AC 32 ms 1340 KB
small_5.txt AC 30 ms 1284 KB
small_6.txt AC 32 ms 1284 KB
small_7.txt AC 31 ms 1348 KB
small_8.txt AC 30 ms 1340 KB
small_9.txt AC 32 ms 1220 KB
star_0.txt AC 314 ms 27760 KB
star_1.txt AC 311 ms 27760 KB
star_2.txt AC 314 ms 27736 KB
tencluster_0.txt AC 239 ms 10304 KB
tencluster_1.txt AC 241 ms 10152 KB
tencluster_2.txt AC 235 ms 10032 KB
tencluster_3.txt AC 240 ms 10376 KB
tencluster_4.txt AC 242 ms 10276 KB
tree_0.txt AC 372 ms 27188 KB
tree_1.txt AC 374 ms 27168 KB
tree_2.txt AC 371 ms 27188 KB
verysmall_0.txt AC 32 ms 1220 KB
verysmall_1.txt AC 31 ms 1180 KB
verysmall_2.txt AC 32 ms 1260 KB
verysmall_3.txt AC 32 ms 1204 KB
verysmall_4.txt AC 31 ms 1200 KB
verysmall_5.txt AC 32 ms 1204 KB
verysmall_6.txt AC 31 ms 1184 KB
verysmall_7.txt AC 29 ms 1220 KB
verysmall_8.txt AC 31 ms 1220 KB
verysmall_9.txt AC 33 ms 1292 KB