QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#423011 | #7177. Many Many Cycles | HHH666 | WA | 0ms | 3712kb | C++14 | 3.4kb | 2024-05-27 20:48:35 | 2024-05-27 20:48:35 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define i1 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define all(v) v.begin(), v.end()
using namespace std;
template<typename types>
void read(types &x) {
x = 0; char c = getchar(); int f = 1;
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f; return;
}
void read() {}
template<typename types, typename... Args>
void read(types &x, Args&... args) {
read(x), read(args...);
return;
}
template<typename types>
void write(types x) {
if (x < 0) putchar('-'), x = -x;
types k = x / 10;
if (k) write(k);
putchar(x - k * 10 + '0');
return;
}
void print() { puts(""); }
template<typename types, typename... Args>
void print(types x, Args... args) {
write(x), putchar(' '), print(args...);
return;
}
const int MAXN = 1e4 + 10;
const int MAXM = 2e4 + 10;
const int LGN = 20;
int n, m;
struct Edge {
int x, y, w;
} e[MAXM];
int head[MAXN], to[MAXM], w[MAXM], nxt[MAXM], idx = 1;
ll depth[MAXN], d[MAXN];
int dfn[MAXN], pa[MAXN], rk[MAXN], mn[MAXN][LGN], lg[MAXN], timecnt;
int cmp(int x, int y) { return d[x] < d[y] ? x : y; }
void addedge(int x, int y, int z) {
nxt[++idx] = head[x];
to[idx] = y;
w[idx] = z;
head[x] = idx;
return;
}
int query(int l, int r) {
int k = lg[r - l + 1];
return cmp(mn[l][k], mn[r - (1 << k) + 1][k]);
}
int lca(int x, int y) {
if (x == y) return x;
if (dfn[x] > dfn[y]) swap(x, y);
return pa[query(dfn[x] + 1, dfn[y])];
}
void dfs(int x) {
dfn[x] = ++timecnt, rk[dfn[x]] = x;
mn[rk[x]][0] = x;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (!dfn[y]) depth[y] = depth[x] + w[i], d[y] = d[x] + 1, pa[y] = x, dfs(y);
}
return;
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int main() {
ios:: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
read(n, m);
for (int i = 1; i <= m; ++i) {
int x, y, z; read(x, y, z);
addedge(x, y, z), addedge(y, x, z);
e[i].x = x, e[i].y = y, e[i].w = z;
}
dfs(1);
for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for (int k = 1; k <= lg[n]; ++k)
for (int i = 1; i + (1 << k) - 1 <= n; ++i)
mn[i][k] = cmp(mn[i][k - 1], mn[i + (1 << (k - 1))][k - 1]);
ll g = -1;
for (int i = 1; i <= m; ++i) {
if (depth[e[i].x] > depth[e[i].y]) swap(e[i].x, e[i].y);
int x = e[i].x, y = e[i].y, w = e[i].w;
if (pa[y] == x) continue;
ll t = depth[y] - depth[x] + w;
if (~g) g = gcd(g, t);
else g = t;
}
if (g == -1) { print(0); return 0; }
for (int i = 1; i <= m; ++i) {
int x1 = e[i].x, y1 = e[i].y;
if (pa[y1] == x1) continue;
for (int j = i + 1; j <= m; ++j) {
int x2 = e[j].x, y2 = e[j].y;
if (pa[y2] == x2) continue;
int l = lca(y1, y2);
if (dfn[x1] < dfn[x2]) swap(x1, x2);
int x = x1;
if (lca(x, l) != x) continue;
g = gcd(g, depth[y1] - depth[x1] + depth[y2] - depth[x2] + e[i].w + e[j].w + 2 * (depth[l] - depth[x]));
}
}
print(g);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
4 4 1 2 1 2 3 1 3 4 1 4 1 1
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 5 1 2 1 1 3 2 1 4 1 2 3 1 3 4 1
output:
4
result:
ok answer is '4'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3692kb
input:
20 50 1 2 8 1 3 1 3 4 5 3 5 9 3 6 5 6 7 6 7 8 8 2 9 2 8 10 3 8 11 7 8 12 5 3 13 4 7 14 3 6 15 7 9 16 6 8 17 7 16 18 9 16 19 3 18 20 10 11 3 2 17 1 1 16 2 2 15 1 1 10 3 2 9 1 2 19 2 1 6 1 2 7 3 1 17 3 2 15 3 2 8 6 2 5 1 2 8 1 2 12 1 1 12 7 1 4 1 2 18 2 1 11 7 1 14 1 1 18 1 1 18 9 1 10 6 1 14 3 2 20 2...
output:
1
result:
wrong answer expected '2', found '1'