Untitled

Dorijanko

Oct 11th, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

text 1.88 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
#define X first
#define Y second
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=10010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n, m;
vector < pii > v[N];
ll dep[N], d;
int par[N][15], deep[N];
vector < pii > luk;
vector < int > smece;
void dfs(int x, int lst) {
par[x][0] = lst;
for(int j = 1;j < 15;j++)
par[x][j] = par[par[x][j - 1]][j - 1];
cout << x << " " << lst << endl;
for(pii tmp : v[x]) {
if(tmp.Y == lst) continue;
if(dep[tmp.Y] != -1 && dep[tmp.Y] < dep[x]) {
luk.pb({x, tmp.Y});
smece.pb(tmp.X);
} else if(dep[tmp.Y] == -1) {
dep[tmp.Y] = dep[x] + tmp.X;
deep[tmp.Y] = deep[x] + 1;
dfs(tmp.Y, x);
}
}
}
int digni(int x, int k){
for(int j = 0;j < 15;j++)
if(k & (1 << j)) x = par[x][j];
return x;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dep, -1, sizeof(dep));
cin >> n >> m;
for(int i = 0;i < m;i++) {
int a, b, c; scanf("%d%d%d", &a, &b, &c);
v[a].pb({c, b});
v[b].pb({c, a});
}
ll d = 0;
for(int x = 1;x <= n;x++) {
if(dep[x] != -1) continue;
dep[x] = 0; dfs(x, x); deep[x] = 0;
for(int i = 0;i < (int)luk.size();i++) {
// cout << " luk " << luk[i].x << " " << luk[i].y << std::endl;
d = gcd(d, dep[luk[i].x] - dep[luk[i].y] + smece[i]);
for(int j = 0;j < (int)luk.size();j++) {
if(i == j) continue;
if(dep[luk[i].y] > dep[luk[j].y]) continue;
if(dep[luk[i].x] > dep[luk[j].x]) continue;
if(dep[luk[j].y] > dep[luk[i].x]) continue;
if(digni(luk[j].x, deep[luk[j].x] - deep[luk[i].x]) != luk[i].x) continue;
d = gcd(d, dep[luk[i].x] - dep[luk[j].y]);
}
}
luk.clear(); smece.clear();
}
cout << d << endl;
}

Add Comment

Please, Sign In to add comment