oj.uz

Submission #382188

# Submission time Handle Problem Language Result Execution time Memory
382188 2021-03-26T16:28:51 Z mohamedsobhi777 Cheap flights (LMIO18_pigus_skrydziai) C++14
0 / 100
 3000 ms 115764 KB 
#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;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16756 KB Output is correct
2 Correct 12 ms 16748 KB Output is correct
3 Correct 12 ms 16768 KB Output is correct
4 Correct 12 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Execution timed out 3065 ms 23576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16756 KB Output is correct
2 Correct 12 ms 16748 KB Output is correct
3 Correct 12 ms 16768 KB Output is correct
4 Correct 12 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Execution timed out 3065 ms 23576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 52140 KB Output is correct
2 Correct 1071 ms 85404 KB Output is correct
3 Correct 266 ms 39652 KB Output is correct
4 Correct 410 ms 55772 KB Output is correct
5 Execution timed out 3060 ms 115764 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 52140 KB Output is correct
2 Correct 1071 ms 85404 KB Output is correct
3 Correct 266 ms 39652 KB Output is correct
4 Correct 410 ms 55772 KB Output is correct
5 Execution timed out 3060 ms 115764 KB Time limit exceeded
6 Halted 0 ms 0 KB -