Submission #382192

#	Time	Username	Problem	Language	Result	Execution time	Memory
382192		mohamedsobhi777	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	1981 ms	152856 KiB

pigus_skrydziai

#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;
                     }
              }
       }
       if (x != p)
       {
              for (auto u : adj2[x])
              {
                     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;
}

• Subtask 1: 12 / 12
• Subtask 2: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 47 / 47