Submission #1149514


Source Code Expand

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

int n, m; // number of nodes, edges

vvi edge;  // list of edges
vvi g;     // link-list of graph
vi prenum; // order of reached node
vi lowest; //
vi parent; // based on prenum(order)
int timer;

void lowlink_dfs(int u, int prev) {
  prenum[u] = timer;
  lowest[u] = timer;
  timer += 1;

  for (auto v : g[u]) {
    if (prenum[v] < 0) {
      parent[v] = u;
      lowlink_dfs(v, u);
      lowest[u] = min(lowest[u], lowest[v]);
    } else if (v != prev) {
      lowest[u] = min(lowest[u], prenum[v]);
    }
  }
}

void lowlink() {
  prenum.assign(n, -1);
  lowest.assign(n, 0);
  parent.assign(n, 0);
  timer = 0;
  lowlink_dfs(0, -1);
}

bool is_bridge(int x, int y) {
  return (prenum[x] < lowest[y] || prenum[y] < lowest[x]);
}

set<pii> bridge() {
  set<pii> ret;
  FOR(i, 1, n) {
    if (prenum[parent[i]] < lowest[i]) {
      int mi = min(parent[i], i);
      int ma = max(parent[i], i);
      ret.insert(make_pair(mi, ma));
    }
  }
  return ret;
}

struct UF {
  vector<int> par; // parent
  vector<int> sizes;
  UF(int n) : par(n), sizes(n, 1) {
    for (int i = 0; i < n; ++i) {
      par[i] = i;
    }
  }
  int root(int x) {
    if (x == par[x]) {
      return x;
    }
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (sizes[x] < sizes[y]) {
      swap(x, y);
    }
    par[y] = x;
    sizes[x] += sizes[y];
    sizes[y] = 0;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return sizes[root(x)];
  }
};

// query
int n_component;
vi roots;
vi group_id;
vi depth;
vvi par;
int MAX_LOG_V = 40;

void dfs(int u, int prev, int d) {
  depth[u] = d;
  par[0][u] = prev;
  for (int v : g[u]) {
    if (v == prev) {
      continue;
    }
    dfs(v, u, d+1);
  }
}

void lca_init() {
  dfs(0, -1, 0);
  rep (k, MAX_LOG_V - 1) {
    rep (i, n_component) {
      if (par[k][i] < 0) {
        continue;
      } else {
        par[k+1][i] = par[k][par[k][i]];
      }
    }
  }
}

int lca(int u, int v) {
  if (depth[u] > depth[v]) {
    swap(u, v);
  }
  rep (k, MAX_LOG_V) {
    if ((((depth[v] - depth[u]) >> k) & 1) == 1) {
      v = par[k][v];
    }
  }
  if (u == v) { return u; }
  for (int k = MAX_LOG_V - 1; k >= 0; --k) {
    if (par[k][u] != par[k][v]) {
      u = par[k][u];
      v = par[k][v];
    }
  }
  return par[0][u];
}

int main() {
  scanf("%d %d", &n, &m);
  edge.assign(m, vi(2, 0));
  g.resize(n);
  rep (i, m) {
    int x, y;
    scanf("%d %d", &x, &y);
    x -= 1; y -= 1;
    if (x > y) {
      swap(x, y);
    }
    edge[i][0] = x;
    edge[i][1] = y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  lowlink();
  auto bridges = bridge();
  UF uf(n);
  rep (i, m) {
    if (!is_bridge(edge[i][0], edge[i][1])) {
      uf.unite(edge[i][0], edge[i][1]);
    }
  }

  set<int> roots_set;
  rep (i, n) {
    roots_set.insert(uf.root(i));
  }
  n_component = (int)roots_set.size();
  roots.assign(n_component, 0);
  group_id.assign(n, -1);
  {
    auto itr = begin(roots_set);
    for (int i = 0; itr != end(roots_set); ++i, ++itr) {
      roots[i] = *itr;
      group_id[roots[i]] = i;
    }
  }
  rep (i, n) {
    group_id[i] = group_id[uf.root(i)];
  }

  g.clear();
  g.resize(n_component);
  for (auto b : bridges) {
    int u = group_id[b.first];
    int v = group_id[b.second];
    g[u].push_back(v);
    g[v].push_back(u);
  }
  depth.assign(n_component, 0);
  par.assign(MAX_LOG_V, vi(n_component, -1));
  lca_init();

  int q;
  scanf("%d", &q);
  int a, b, c;
  rep (query, q) {
    scanf("%d%d%d", &a, &b, &c);
    a = group_id[a-1];
    b = group_id[b-1];
    c = group_id[c-1];

    int r = lca(a, c);
    int ra = lca(a, b);
    int rc = lca(c, b);

    if ((ra == b && rc == r) || (ra == r && rc == b)) {
      printf("OK\n");
    } else {
      printf("NG\n");
    }
  }

  return 0;
}

Submission Info

Submission Time
Task D - 旅行会社高橋君
User tspcx
Language C++14 (Clang 3.8.0)
Score 100
Code Size 4947 Byte
Status AC
Exec Time 597 ms
Memory 44288 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 80
Set Name Test Cases
Sample sample_0.txt, sample_1.txt, sample_2.txt
All 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, sample_0.txt, sample_1.txt, sample_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
Case Name Status Exec Time Memory
bigcycleandsub_0.txt AC 112 ms 19584 KB
bigcycleandsub_1.txt AC 114 ms 19456 KB
cluster_0.txt AC 156 ms 20480 KB
cluster_1.txt AC 152 ms 20480 KB
cluster_2.txt AC 156 ms 20352 KB
cluster_3.txt AC 162 ms 20480 KB
cluster_4.txt AC 154 ms 20480 KB
cycleline_0.txt AC 179 ms 16128 KB
cycleline_1.txt AC 208 ms 16128 KB
cycleline_2.txt AC 233 ms 16128 KB
cycleline_3.txt AC 235 ms 16128 KB
cycleline_4.txt AC 238 ms 16128 KB
cycletree_0.txt AC 297 ms 16000 KB
cycletree_1.txt AC 303 ms 15872 KB
cycletree_2.txt AC 300 ms 15872 KB
cycletree_3.txt AC 294 ms 16000 KB
cycletree_4.txt AC 302 ms 16000 KB
large_0.txt AC 128 ms 22400 KB
large_1.txt AC 23 ms 3712 KB
large_2.txt AC 93 ms 18560 KB
line_0.txt AC 248 ms 44288 KB
line_1.txt AC 184 ms 43264 KB
lineandsub_0.txt AC 458 ms 42880 KB
lineandsub_1.txt AC 371 ms 43776 KB
lineandsub_2.txt AC 417 ms 43392 KB
maxrand_0.txt AC 145 ms 25216 KB
maxrand_1.txt AC 146 ms 25216 KB
maxrand_2.txt AC 146 ms 25216 KB
maxrandandsub_0.txt AC 157 ms 25472 KB
maxrandandsub_1.txt AC 162 ms 25472 KB
maxrandandsub_2.txt AC 156 ms 25472 KB
maxrandandsub_3.txt AC 150 ms 25472 KB
maxrandandsub_4.txt AC 156 ms 25472 KB
med_0.txt AC 2 ms 384 KB
med_1.txt AC 1 ms 256 KB
med_2.txt AC 2 ms 384 KB
med_3.txt AC 2 ms 384 KB
med_4.txt AC 2 ms 512 KB
med_5.txt AC 2 ms 512 KB
med_6.txt AC 2 ms 512 KB
med_7.txt AC 2 ms 512 KB
med_8.txt AC 1 ms 256 KB
med_9.txt AC 2 ms 384 KB
perfect_0.txt AC 41 ms 6016 KB
perfect_1.txt AC 28 ms 6528 KB
perfect_2.txt AC 41 ms 6272 KB
sample_0.txt AC 1 ms 256 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
small_0.txt AC 2 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 2 ms 256 KB
small_5.txt AC 1 ms 256 KB
small_6.txt AC 1 ms 256 KB
small_7.txt AC 1 ms 256 KB
small_8.txt AC 2 ms 256 KB
small_9.txt AC 1 ms 256 KB
star_0.txt AC 430 ms 40688 KB
star_1.txt AC 433 ms 40688 KB
star_2.txt AC 447 ms 40816 KB
tencluster_0.txt AC 144 ms 21120 KB
tencluster_1.txt AC 157 ms 20864 KB
tencluster_2.txt AC 157 ms 20864 KB
tencluster_3.txt AC 152 ms 21248 KB
tencluster_4.txt AC 155 ms 21248 KB
tree_0.txt AC 597 ms 39936 KB
tree_1.txt AC 588 ms 39936 KB
tree_2.txt AC 588 ms 39936 KB
verysmall_0.txt AC 1 ms 256 KB
verysmall_1.txt AC 1 ms 256 KB
verysmall_2.txt AC 1 ms 256 KB
verysmall_3.txt AC 1 ms 256 KB
verysmall_4.txt AC 1 ms 256 KB
verysmall_5.txt AC 1 ms 256 KB
verysmall_6.txt AC 1 ms 256 KB
verysmall_7.txt AC 1 ms 256 KB
verysmall_8.txt AC 1 ms 256 KB
verysmall_9.txt AC 1 ms 256 KB