QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217603 | #7177. Many Many Cycles | Lain | WA | 0ms | 3548kb | C++20 | 2.8kb | 2023-10-17 02:19:11 | 2023-10-17 02:19:11 |
Judging History
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'