oj.uz

Submission #950290

# Submission time Handle Problem Language Result Execution time Memory
950290 2024-03-20T07:45:19 Z abczz Duathlon (APIO18_duathlon) C++14
31 / 100
 222 ms 36428 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 * 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 4 ms 8792 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 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 2 ms 8792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 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 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 2 ms 8792 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 90 ms 32236 KB Output is correct
2 Correct 95 ms 32160 KB Output is correct
3 Correct 137 ms 30308 KB Output is correct
4 Correct 156 ms 31124 KB Output is correct
5 Correct 121 ms 26392 KB Output is correct
6 Correct 182 ms 28792 KB Output is correct
7 Correct 167 ms 24204 KB Output is correct
8 Correct 153 ms 26312 KB Output is correct
9 Correct 185 ms 22020 KB Output is correct
10 Correct 148 ms 23572 KB Output is correct
11 Correct 142 ms 18656 KB Output is correct
12 Correct 111 ms 18260 KB Output is correct
13 Correct 115 ms 17844 KB Output is correct
14 Correct 107 ms 17748 KB Output is correct
15 Correct 74 ms 16212 KB Output is correct
16 Correct 73 ms 16212 KB Output is correct
17 Correct 5 ms 9844 KB Output is correct
18 Correct 5 ms 9820 KB Output is correct
19 Correct 5 ms 9820 KB Output is correct
20 Correct 6 ms 10076 KB Output is correct
21 Correct 5 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 8792 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 3 ms 8828 KB Output is correct
4 Correct 3 ms 9048 KB Output is correct
5 Correct 3 ms 9304 KB Output is correct
6 Correct 3 ms 9052 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 8892 KB Output is correct
10 Correct 3 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 3 ms 8796 KB Output is correct
13 Correct 4 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 3 ms 8796 KB Output is correct
18 Correct 3 ms 8796 KB Output is correct
19 Correct 3 ms 9052 KB Output is correct
20 Correct 3 ms 9048 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 30368 KB Output is correct
2 Correct 176 ms 30272 KB Output is correct
3 Correct 177 ms 31292 KB Output is correct
4 Correct 172 ms 30524 KB Output is correct
5 Correct 163 ms 30288 KB Output is correct
6 Correct 180 ms 36428 KB Output is correct
7 Correct 183 ms 34280 KB Output is correct
8 Correct 192 ms 33352 KB Output is correct
9 Correct 170 ms 32304 KB Output is correct
10 Correct 222 ms 26776 KB Output is correct
11 Correct 162 ms 29352 KB Output is correct
12 Correct 157 ms 24384 KB Output is correct
13 Correct 149 ms 23748 KB Output is correct
14 Correct 126 ms 20128 KB Output is correct
15 Correct 131 ms 19216 KB Output is correct
16 Correct 63 ms 15956 KB Output is correct
17 Correct 161 ms 30692 KB Output is correct
18 Correct 142 ms 30644 KB Output is correct
19 Correct 157 ms 31136 KB Output is correct
20 Correct 180 ms 30624 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 3 ms 9000 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 184 ms 31036 KB Output is correct
2 Correct 175 ms 30140 KB Output is correct
3 Incorrect 147 ms 21064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 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 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 2 ms 8792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8792 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 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Incorrect 2 ms 8792 KB Output isn't correct
8 Halted 0 ms 0 KB -