QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414715#7177. Many Many CyclespandapythonerWA 1ms3824kbC++206.8kb2024-05-19 15:41:422024-05-19 15:41:43

Judging History

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

  • [2024-05-19 15:41:43]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3824kb
查看
  • [2024-05-19 15:41:42]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;

#define int long long
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


struct DSU {
    int n;
    vector<int> t;


    void build(int _n) {
        n = _n;
        t.resize(n);
        for (int i = 0; i < n; i += 1) {
            t[i] = i;
        }
    }


    int get(int v) {
        if (t[v] == v) {
            return v;
        }
        return t[v] = get(t[v]);
    }


    void merge(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return;
        }
        t[a] = b;
    }
};

struct edge {
    int to;
    ll w;
    int i;
};


int n, m;
vector<vector<edge>> g;
vector<vector<edge>> rg;
vector<ll> clr;
DSU dsu;
vector<ll> h;
vector<ll> up;


void components_dfs(int v, int p, int pi, int mh) {
    h[v] = mh;
    up[v] = mh;
    for (auto [to, w, i] : g[v]) {
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            if (h[to] < h[v] and pi != -1) {
                dsu.merge(i, pi);
            }
            up[v] = min(up[v], h[to]);
            continue;
        }
        components_dfs(to, v, i, mh + 1);
        up[v] = min(up[v], up[to]);
        if (up[to] < h[v]) {
            if (pi != -1) {
                dsu.merge(i, pi);
            }
        }
    }
}


bool paint(int from, int to, int i, ll mw, ll k) {
    for (auto [toto, w, j] : g[to]) {
        if (toto == from or dsu.get(i) != dsu.get(j)) {
            continue;
        }
        if (clr[j] != -1) {
            if (clr[j] != (clr[i] + w) % k) {
                return false;
            }
            continue;
        }
        clr[j] = (clr[i] + w) % k;
        if (!paint(to, toto, j, w, k)) {
            return false;
        }
    }
    for (auto [fromfrom, w, j] : rg[from]) {
        if (fromfrom == to or dsu.get(i) != dsu.get(j)) {
            continue;
        }
        if (clr[j] != -1) {
            if (clr[i] != (clr[j] + mw) % k) {
                return false;
            }
            continue;
        }
        clr[j] = ((clr[i] - mw) % k + k) % k;
        if (!paint(fromfrom, from, j, w, k)) {
            return false;
        }
    }
    return true;
}


bool check(ll k) {
    clr.assign(m + m, -1);
    for (int from = 0; from < n; from += 1) {
        for (auto [to, w, i] : g[from]) {
            if (clr[i] != -1) {
                continue;
            }
            clr[i] = 0;
            if (!paint(from, to, i, w, k)) {
                return false;
            }
        }
    }
    return true;
}


ll dfs(int v, int p, ll mh) {
    h[v] = mh;
    for (auto [to, w, _] : g[v]) {
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            return h[v] - h[to] + w;
        }
        ll x = dfs(to, v, mh + w);
        if (x != -1) {
            return x;
        }
    }
    return -1;
}

ll find_cycle() {
    h.assign(n, -1);
    for (int v = 0; v < n; v += 1) {
        if (h[v] == -1) {
            ll x = dfs(v, -1, 0);
            if (x != -1) {
                return x;
            }
        }
    }
    return -1;
}



ll solve() {
    dsu.build(2 * m);
    for (int i = 0; i < m; i += 1) {
        dsu.merge(2 * i, 2 * i + 1);
    }
    h.assign(n, -1);
    up.assign(n, -1);
    for (int v = 0; v < n; v += 1) {
        if (h[v] == -1) {
            components_dfs(v, -1, -1, 0);
        }
    }
    ll c = find_cycle();
    if (c == -1) {
        return 0;
    }
    ll val = 1;
    for (ll i = 2; i * i <= c; i += 1) {
        while (c % i == 0) {
            c /= i;
            if (check(val * i)) {
                val *= i;
            }
        }
    }
    if (c > 1) {
        if (check(val * c)) {
            val *= c;
        }
        c = 1;
    }
    return val;
}


void stupid_dfs(int v, int p, ll mask, ll mh, ll& rs) {
    h[v] = mh;
    for (auto [to, w, i] : g[v]) {
        i /= 2;
        if ((mask >> i) % 2 == 0) {
            continue;
        }
        if (to == p) {
            continue;
        }
        if (h[to] != -1) {
            if (h[to] < h[v]) {
                rs = h[v] - h[to] + w;
            }
            continue;
        }
        stupid_dfs(to, v, mask, mh + w, rs);
    }
}


ll solve_slow() {
    ll rs = 0;
    for (ll mask = 0; mask < (1 << m); mask += 1) {
        h.assign(n, -1);
        for (int v = 0; v < n; v += 1) {
            if (h[v] != -1) {
                continue;
            }
            ll x = -1;
            stupid_dfs(v, -1, mask, 0, x);
            if (x != -1) {
                rs = gcd(rs, x);
            }
        }
    }
    return rs;
}


void gen_test(int maxn = 20, int maxm = 20, int maxc = 1) {
    n = rnd() % (maxn - 1) + 2;
    maxm = min(maxm, n * (n - 1) / 2);
    m = rnd() % maxm + 1;
    set<pair<int, int>> st;
    g.assign(n, vector<edge>());
    rg.assign(n, vector<edge>());
    for (int i = 0; i < m; i += 1) {
        int u = rnd() % n;
        int v = rnd() % n;
        while (st.find(make_pair(u, v)) != st.end() || u == v) {
            u = rnd() % n;
            v = rnd() % n;
        }
        st.insert(make_pair(u, v));
        st.insert(make_pair(v, u));
        int c = rnd() % maxc + 1;
        g[u].push_back(edge{ v, c, 2 * i });
        rg[v].push_back(edge{ u, c, 2 * i });
        g[v].push_back(edge{ u, c, 2 * i + 1 });
        rg[u].push_back(edge{ v, c, 2 * i + 1 });
    }
}


void print_test() {
    cout << n << " " << m << "\n";
    for (int v = 0; v < n; v += 1) {
        for (auto [to, w, i] : g[v]) {
            if (i % 2 == 0) {
                cout << v + 1 << " " << to + 1 << " " << w << "\n";
            }
        }
    }
}

void stress() {
    int c = 0;
    while (1) {
        cout << ++c << "\n";
        gen_test();
        ll right_rs = solve_slow();
        ll my_rs = solve();
        if (right_rs != my_rs) {
            print_test();
            break;
        }
    }
}


int32_t main() {
    // stress();
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    cin >> n >> m;
    g.assign(n, vector<edge>());
    rg.assign(n, vector<edge>());
    for (int i = 0; i < m; i += 1) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        --u;
        --v;
        g[u].push_back(edge{ v, c, 2 * i });
        rg[v].push_back(edge{ u, c, 2 * i });
        g[v].push_back(edge{ u, c, 2 * i + 1 });
        rg[u].push_back(edge{ v, c, 2 * i + 1 });
    }
    ll rs = solve();
    cout << rs << "\n";
    return 0;
}

/*
5 5
1 2 1
1 3 1
1 4 1
2 4 1
4 5 1

*/
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3732kb

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: 3536kb

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: 0
Accepted
time: 0ms
memory: 3548kb

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:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

20 50
1 2 18468
1 3 26501
3 4 15725
3 5 29359
3 6 24465
6 7 28146
7 8 16828
2 9 492
8 10 11943
8 11 5437
8 12 14605
3 13 154
7 14 12383
6 15 18717
9 16 19896
8 17 21727
16 18 11539
16 19 19913
18 20 26300
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 ...

output:

1

result:

ok answer is '1'

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3824kb

input:

100 150
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

1

result:

wrong answer expected '3', found '1'
English 繁體中文 简体中文

伺服器時間: 2024-12-05 08:03:58 | 開源專案