QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217603#7177. Many Many CyclesLainWA 0ms3548kbC++202.8kb2023-10-17 02:19:112023-10-17 02:19:11

Judging History

你现在查看的是最新测评结果

  • [2023-10-17 02:19:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3548kb
  • [2023-10-17 02:19:11]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  struct edge {
    int u, v, w, is_span;
    int to(int x) {
      return u^v^x;
    }
  };

  int n, m;
  cin >> n >> m;
  vector<edge> edges;
  edges.reserve(m);
  vector<vi> g(n);
  rep(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    u--,v--;
    g[u].push_back(sz(edges));
    g[v].push_back(sz(edges));
    edges.push_back({u,v,w,0});
  }


  const int B = 13;
  vector<vi> up(n, vi(B));
  int comp_num = 0;
  vi vis(n), comp(n), dep(n);
  vector<ll> dist(n);
  auto dfs = [&](auto& self, int s, int p)->void {
    up[s][0] = p;
    rep(j, 1, B) up[s][j] = up[up[s][j-1]][j-1];
    vis[s] = 1;
    comp[s] = comp_num;
    for (auto& e : g[s]) {
      int u = edges[e].to(s);
      if (vis[u]) continue;
      edges[e].is_span = 1;
      dist[u] = dist[s] + edges[e].w;
      dep[u] = dep[s]+1;
      self(self, u, s);
    }
  };
  rep(i, 0, n)  {
    if (!vis[i]) {
      dfs(dfs, i, i);
      comp_num++;
    }
  }

  vector<vi> memo(n, vi(n, -1));
  auto lca = [&](int x, int y)->int {
    if (memo[x][y] != -1) return memo[x][y];
    if (dep[x] > dep[y]) swap(x, y);
    if (x == y) return x;
    int diff = dep[y] - dep[x];
    rep(j, 0, B) {
      if (diff>>j&1) y = up[y][j];
    }
    if (x == y) return memo[x][y] = memo[y][x] = x;
    for (int j = B-1; j >= 0; j--) {
      if (up[x][j] != up[y][j]) {
        x = up[x][j], y = up[y][j];
      }
    }
    return memo[x][y] = memo[y][x] = up[x][0];
  };

  vi not_span;
  rep(i, 0, m) if (edges[i].is_span) not_span.push_back(i);

  ll ans = 0;
  for (auto& i : not_span) {
    auto& [u,v, w, _] = edges[i];

    if (dep[u] > dep[v]) swap(u, v); // u above v
    
    // Simple cycle
    ans = __gcd(ans, dist[v] - dist[u] + w);

    // xored
    for (auto& j : not_span) {
      auto& [a, b, w1, _] = edges[j];
      if (comp[a] != comp[u]) continue; // not in the same component, ignore
      if (dep[a] > dep[b]) swap(a, b); // a above b
      if (dep[b] <= dep[u]) continue; // no intersection, b above u
      int upper = dep[a] < dep[u] ? a : u;
      int lower = dep[a] > dep[u] ? a : u;
      if (lca(upper, lower) != upper) continue; // no shared edges
      int l = lca(v, b);
      if (dep[l] <= dep[lower]) continue;
      ans = __gcd(ans, 2*(dist[l] - dist[lower]));
    }
  }
  cout << ans << '\n';
}


详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3548kb

input:

4 4
1 2 1
2 3 1
3 4 1
4 1 1

output:

2

result:

wrong answer expected '4', found '2'