QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423011#7177. Many Many CyclesHHH666WA 0ms3712kbC++143.4kb2024-05-27 20:48:352024-05-27 20:48:35

Judging History

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

  • [2024-05-27 20:48:35]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3712kb
  • [2024-05-27 20:48:35]
  • 提交

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'