oj.uz

Submission #951292

# Submission time Handle Problem Language Result Execution time Memory
951292 2024-03-21T14:55:22 Z abczz Duathlon (APIO18_duathlon) C++14
0 / 100
 120 ms 46012 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, k, a, b, g, cnt, f, rt, apcnt, low[100000], st[100000], sz[200000], dp[200000];
vector <ll> G, blocks;
bool ap[100000];
vector <ll> V, adj[100000], X[100000], E[200000];

void tar(ll u, ll p) {
  G.push_back(u);
  st[u] = low[u] = ++cnt;
  V.push_back(u);
  ll rch = 0;
  for (auto v : adj[u]) {
    if (!st[v]) {
      ++rch;
      tar(v, u);
      low[u] = min(low[u], low[v]);
      if (p != -1 && low[v] >= st[u]) ap[u] = 1;
      if (low[v] >= st[u]) {
        blocks.push_back(k);
        while (!V.empty()) {
          auto x = V.back();
          V.pop_back();
          X[x].push_back(k);
          ++sz[k];
          if (x == v) break;
        }
        X[u].push_back(k);
        ++sz[k];
        ++k;
      }
    }
    else if (v != p) {
      low[u] = min(low[u], st[v]);
    }
  }
  if (p == -1 && rch > 1) ap[u] = 1;
}

void calc(ll u, ll p) {
  //cout << u << '\n';
  if (u >= n) dp[u] = sz[u] - E[u].size();
  else dp[u] = 1;
  //cout << u << " " << dp[u] << '\n';
  for (auto v : E[u]) {
    if (v != p) {
      calc(v, u);
      dp[u] += dp[v];
      if (u >= n) {
        //cout << (sz[u]-E[u].size()) << " " << (dp[v] - 1) << " " << sz[u] << '\n';
        //cout << u << '\n';
        f += (sz[u] - E[u].size()) * (sz[u] - 2) * (dp[v] - 1) * 2;
        f += (sz[u] - E[u].size()) * (G.size() - sz[u] - dp[v] + 1) * (dp[v]-1) * 2;
      }
    }
  }
  for (auto v : E[u]) {
    if (v != p) {
      if (u < n) {
        f += dp[v] * (G.size() - dp[v] - 1);
      }
    }
  }
  if (u < n) {
    f += (G.size() - dp[u]) * (dp[u] - 1);
  }
  else {
    //cout << sz[u] - E[u].size() << " " << sz[u]-2 << " " << (ll)G.size()-dp[u]-1 << '\n';
    f += (sz[u] - E[u].size()) * (sz[u] - 2) * (G.size() - dp[u] - (p != -1)) * 2;
  }
}

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);
  }
  k = n;
  for (int i=0; i<n; ++i) {
    if (!st[i]) {
      G.clear();
      blocks.clear();
      V.clear();
      tar(i, -1);
      apcnt = 0;
      for (auto u : G) {
        if (ap[u]) {
          ++apcnt;
          for (auto v : X[u]) {
            E[u].push_back(v);
            E[v].push_back(u);
          }
        }
      }
      for (auto u : blocks) {
        if (sz[u] >= 3) {
          f += (sz[u] - E[u].size()) * (sz[u]-1) * (sz[u]-2);
          f += E[u].size() * (sz[u]-1) * (sz[u]-2);
        }
      }
      calc(blocks[0], -1);
    }
  }
  cout << f << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 31224 KB Output is correct
2 Correct 86 ms 31284 KB Output is correct
3 Correct 90 ms 33984 KB Output is correct
4 Correct 90 ms 30776 KB Output is correct
5 Correct 92 ms 29868 KB Output is correct
6 Correct 97 ms 35272 KB Output is correct
7 Correct 95 ms 29356 KB Output is correct
8 Correct 102 ms 32136 KB Output is correct
9 Correct 114 ms 28036 KB Output is correct
10 Correct 87 ms 28220 KB Output is correct
11 Incorrect 68 ms 23380 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 3 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 3 ms 13148 KB Output is correct
8 Correct 3 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 3 ms 12936 KB Output is correct
14 Incorrect 4 ms 12888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 30008 KB Output is correct
2 Correct 102 ms 30264 KB Output is correct
3 Correct 95 ms 30232 KB Output is correct
4 Correct 96 ms 30020 KB Output is correct
5 Correct 94 ms 30012 KB Output is correct
6 Correct 120 ms 46012 KB Output is correct
7 Correct 113 ms 36212 KB Output is correct
8 Correct 115 ms 34620 KB Output is correct
9 Correct 110 ms 32960 KB Output is correct
10 Correct 96 ms 29504 KB Output is correct
11 Correct 102 ms 29976 KB Output is correct
12 Correct 98 ms 29008 KB Output is correct
13 Correct 112 ms 29000 KB Output is correct
14 Incorrect 86 ms 27216 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 30008 KB Output is correct
2 Correct 109 ms 30008 KB Output is correct
3 Incorrect 100 ms 29316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -