This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound
using ll = long long;
using ld = long double;
const int N = 3e5 + 7;
const ll mod = 1e9 + 7;
int n, m;
ll a[N];
int viz[N], col = 1;
ll ans;
map<pii, ll> cost;
vi adj[N];
vi adj2[N];
vii e, e2;
ll disto[N];
int fat[N];
void dfs(int x, int p = 0, int pp = 0)
{
viz[x] = col;
fat[x] = p;
for (auto u : adj[x])
{
if (u == p)
continue;
if (viz[u] != col)
{
dfs(u, x, p);
}
else
{
e2.pb({u, x});
if (p && pp && u == pp)
{
ans = max(ans, cost[{p, pp}] + cost[{x, p}] + cost[{x, pp}]);
}
adj2[x].pb(u);
}
}
}
void dfz(int x, int p)
{
map<int, bool> mp;
for (auto u : adj2[x])
mp[u] = 1;
for (auto u : adj[x])
{
if (fat[u] == x)
{
dfz(u, x);
for (auto v : adj2[u])
{
if (mp.count(v))
{
ans = max(ans, cost[{x, u}] + cost[{x, v}] + cost[{u, v}]);
}
disto[v] = -2e17;
}
}
}
for (auto u : adj2[p])
{
disto[u] = cost[{x, u}];
}
}
void prep(vi &act, vii &e)
{
act.clear();
for (auto u : e)
{
act.pb(u.f);
act.pb(u.s);
}
for (auto u : act)
{
adj[u].clear();
adj2[u].clear();
disto[u] = -2e17;
fat[u] = 0;
}
for (auto u : e)
{
adj[u.f].pb(u.s);
adj[u.s].pb(u.f);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n >> m;
for (int i = 0; i < N; ++i)
disto[i] = -2e17;
vi act;
for (int i = 0; i < m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
a[u] += w;
a[v] += w;
ans = max({ans, a[u], a[v]});
e.pb({u, v});
cost[{u, v}] = cost[{v, u}] = w;
}
while (sz(e))
{
prep(act, e);
for (auto u : act)
{
if (viz[u] != col)
{
dfs(u, 0, 0);
dfz(u, 0);
}
}
e = e2;
e2.clear();
++col;
// break;
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |