oj.uz

Submission #950370

# Submission time Handle Problem Language Result Execution time Memory
950370 2024-03-20T08:53:08 Z abczz Duathlon (APIO18_duathlon) C++14
31 / 100
 189 ms 35384 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define ll long long

using namespace std;

bool visited[100000];
ll n, m, a, b, g, cnt, sz, f, low[100000], st[100000], X[100000];
map <array<ll, 2>, ll> bridge;
vector <ll> G;
vector <array<ll, 2>> bg;
vector <ll> bcc, dp;
vector <ll> adj[100000], E[100000], badj[100000];

void tar(ll u, ll p) {
  G.push_back(u);
  st[u] = low[u] = ++cnt;
  for (auto v : adj[u]) {
    if (!st[v]) {
      tar(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > st[u]) {
        ++bridge[{u, v}];
      }
    }
    else if (v != p) {
      low[u] = min(low[u], st[v]);
    }
  }
}

void dfs(ll u) {
  ++sz;
  X[u] = g;
  visited[u] = 1;
  for (auto v : E[u]) {
    if (!visited[v]) {
      dfs(v);
    }
  }
}

void calc(ll u, ll p) {
  dp[u] = bcc[u];
  for (auto v : badj[u]) {
    if (v != p) {
      calc(v, u);
      dp[u] += dp[v];
    }
  }
}

void solve(ll u, ll p, ll w) {
  ll s = 0;
  for (auto v : badj[u]) {
    if (v != p) {
      s += dp[v];
    }
  }
  f += w * bcc[u] * s * 2;
  w += s;
  for (auto v : badj[u]) {
    if (v != p) {
      f += bcc[u] * dp[v] * (s-dp[v]);
      solve(v, u, w-dp[v]+bcc[u]);
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
    X[i] = -1;
  }
  for (int i=0; i<n; ++i) {
    if (!st[i]) {
      G.clear();
      bg.clear();
      bcc.clear();
      tar(i, -1);
      for (auto u : G) {
        for (auto v : adj[u]) {
          if (bridge.find({u, v}) == bridge.end() && bridge.find({v, u}) == bridge.end()) {
            E[u].push_back(v);
            E[v].push_back(u);
          }
          else bg.push_back({u, v});
        }
      }
      g = 0;
      for (auto u : G) {
        if (!visited[u]) {
          sz = 0;
          dfs(u);
          ++g;
          if (sz >= 3) f += sz * (sz-1) * (sz-2);
          bcc.push_back(sz);
        }
      }
      for (auto sz : bcc) {
        if (sz >= 2) f += (sz-1) * (sz-1) * ((ll)G.size()-sz) * 2;
      }
      dp.resize(bcc.size());
      for (auto [x, y] : bg) {
        badj[X[x]].push_back({X[y]});
      }
      calc(0, -1);
      solve(0, -1, 0);
      for (int i=0; i<g; ++i) badj[i].clear();
    }
  }
  cout << f << '\n';
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:113:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |       for (auto [x, y] : bg) {
      |                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8824 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Incorrect 2 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8824 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Incorrect 2 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 32048 KB Output is correct
2 Correct 109 ms 31708 KB Output is correct
3 Correct 131 ms 29768 KB Output is correct
4 Correct 149 ms 30652 KB Output is correct
5 Correct 130 ms 26080 KB Output is correct
6 Correct 143 ms 28240 KB Output is correct
7 Correct 149 ms 23540 KB Output is correct
8 Correct 159 ms 26052 KB Output is correct
9 Correct 141 ms 21540 KB Output is correct
10 Correct 137 ms 23036 KB Output is correct
11 Correct 103 ms 18260 KB Output is correct
12 Correct 104 ms 18116 KB Output is correct
13 Correct 96 ms 17856 KB Output is correct
14 Correct 93 ms 17488 KB Output is correct
15 Correct 68 ms 16048 KB Output is correct
16 Correct 74 ms 15840 KB Output is correct
17 Correct 5 ms 9816 KB Output is correct
18 Correct 5 ms 10096 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 5 ms 9820 KB Output is correct
21 Correct 4 ms 9820 KB Output is correct
22 Correct 5 ms 9820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 3 ms 9084 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 3 ms 8884 KB Output is correct
15 Correct 3 ms 8796 KB Output is correct
16 Correct 2 ms 8824 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 3 ms 9048 KB Output is correct
20 Correct 3 ms 9052 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 30268 KB Output is correct
2 Correct 169 ms 29880 KB Output is correct
3 Correct 170 ms 30268 KB Output is correct
4 Correct 165 ms 30748 KB Output is correct
5 Correct 181 ms 29884 KB Output is correct
6 Correct 189 ms 35384 KB Output is correct
7 Correct 180 ms 34028 KB Output is correct
8 Correct 188 ms 32824 KB Output is correct
9 Correct 174 ms 32388 KB Output is correct
10 Correct 170 ms 26176 KB Output is correct
11 Correct 166 ms 28720 KB Output is correct
12 Correct 159 ms 23876 KB Output is correct
13 Correct 160 ms 23280 KB Output is correct
14 Correct 144 ms 19616 KB Output is correct
15 Correct 116 ms 18932 KB Output is correct
16 Correct 65 ms 15956 KB Output is correct
17 Correct 160 ms 30336 KB Output is correct
18 Correct 162 ms 30672 KB Output is correct
19 Correct 140 ms 30252 KB Output is correct
20 Correct 145 ms 30104 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 4 ms 8932 KB Output is correct
3 Incorrect 3 ms 8796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 29776 KB Output is correct
2 Correct 168 ms 30092 KB Output is correct
3 Incorrect 141 ms 20544 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8824 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Incorrect 2 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 8824 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Incorrect 2 ms 8796 KB Output isn't correct
8 Halted 0 ms 0 KB -