QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #414715 | #7177. Many Many Cycles | pandapythoner | WA | 1ms | 3824kb | C++20 | 6.8kb | 2024-05-19 15:41:42 | 2024-05-19 15:41:43 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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'