QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199041#7177. Many Many Cyclesucup-team484WA 0ms31120kbC++171.0kb2023-10-03 20:33:132023-10-03 20:33:13

Judging History

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

  • [2023-10-03 20:33:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:31120kb
  • [2023-10-03 20:33:13]
  • 提交

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'