QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199041 | #7177. Many Many Cycles | ucup-team484 | WA | 0ms | 31120kb | C++17 | 1.0kb | 2023-10-03 20:33:13 | 2023-10-03 20:33:13 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
vector<pair<int, int>> adj[N];
int vis[N], dep[N];
ll ans = 0;
void dfs(int u, int p, ll d) {
vis[u] = 1;
for (auto [v, w]: adj[u]) {
if (vis[v]) {
if (dep[u] > dep[v] && v != p)
ans = gcd(ans, d + w);
continue;
}
dep[v] = dep[u] + 1;
dfs(v, u, d + w);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
u--, v--;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
for (int i = 0; i < n; i++)
shuffle(adj[i].begin(), adj[i].end(), rng);
for (int i = 0; i < n; i++) {
fill(vis, vis + n, 0);
fill(dep, dep + n, 0);
dfs(i, -1, 0);
break;
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 30392kb
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: 30004kb
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: 31120kb
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'