oj.uz

Submission #951448

# Submission time Handle Problem Language Result Execution time Memory
951448 2024-03-22T01:30:56 Z abczz Duathlon (APIO18_duathlon) C++14
31 / 100
 154 ms 49084 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) {
        f += (dp[v]-1) * (G.size() - dp[v]); //down -> ap -> up
        f += (dp[v]-1) * (sz[u] - E[u].size()) * (G.size() - dp[v] - 1); //edge -> nonap -> any
        f += (sz[u] - E[u].size()) * (G.size() - dp[v] - 1); //ap -> nonap -> any
        if (p != -1 && sz[u] > 2) {
          f += (dp[v]-1) * (E[u].size()-1) * (sz[u] - 2) * 2; //down -> ap -> down
        }
      }
    }
  }
  for (auto v : E[u]) {
    if (v != p) {
      if (u >= n) {
        if (p != -1 && sz[u] > 2) {
          f += (dp[v]-1) * (dp[u]-sz[u]+1-(dp[v]-1)); //downL -> ap -> downR
        }
      }
    }
  }
  if (u >= n) {
    f += (G.size() - dp[u] - (p != -1)) * dp[u]; //up -> ap -> down
    if (p != -1 && sz[u] > 2) {
      f += (G.size() - dp[u] - 1) * (sz[u] - 1) * (E[u].size()-1) * 2; //up -> ap -> up
    }
    if (sz[u] > 2) {
      f += (sz[u]-1) * (sz[u]-2) * E[u].size(); //down -> ap -> down & up -> ap -> up
    }
    f += (G.size() - dp[u] - (p != -1)) * (sz[u] - E[u].size()) * (dp[u] - 1); //topedge -> nonap -> any
    if (p != -1) f += (sz[u] - E[u].size()) * (dp[u] - 1); //ap -> nonap -> any
    if (G.size() >= 2) {
      f += (sz[u] - E[u].size()) * (sz[u] - (ll)E[u].size() - 1) * (G.size() - 2); //nonap -> nonap -> any
    }
  }
}

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);
      for (auto u : G) {
        if (ap[u]) {
          for (auto v : X[u]) {
            E[u].push_back(v);
            E[v].push_back(u);
          }
        }
      }
      if (!blocks.empty()) calc(blocks[0], -1);
    }
  }
  cout << f << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12888 KB Output is correct
2 Correct 5 ms 12892 KB Output is correct
3 Correct 4 ms 12720 KB Output is correct
4 Correct 4 ms 13044 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Incorrect 2 ms 12888 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 81 ms 31164 KB Output is correct
2 Correct 75 ms 31380 KB Output is correct
3 Correct 98 ms 35624 KB Output is correct
4 Correct 98 ms 31044 KB Output is correct
5 Correct 95 ms 30916 KB Output is correct
6 Correct 129 ms 36800 KB Output is correct
7 Correct 113 ms 29904 KB Output is correct
8 Correct 113 ms 33160 KB Output is correct
9 Correct 121 ms 27728 KB Output is correct
10 Correct 102 ms 28780 KB Output is correct
11 Correct 72 ms 23400 KB Output is correct
12 Correct 77 ms 23376 KB Output is correct
13 Correct 65 ms 22868 KB Output is correct
14 Correct 65 ms 22624 KB Output is correct
15 Correct 49 ms 21052 KB Output is correct
16 Correct 48 ms 20900 KB Output is correct
17 Correct 4 ms 14424 KB Output is correct
18 Correct 5 ms 14428 KB Output is correct
19 Correct 5 ms 14428 KB Output is correct
20 Correct 5 ms 14424 KB Output is correct
21 Correct 4 ms 14428 KB Output is correct
22 Correct 4 ms 14428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 5 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 4 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 5 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12932 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 3 ms 12892 KB Output is correct
19 Correct 4 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 30000 KB Output is correct
2 Correct 105 ms 30192 KB Output is correct
3 Correct 94 ms 30008 KB Output is correct
4 Correct 95 ms 30172 KB Output is correct
5 Correct 96 ms 30104 KB Output is correct
6 Correct 141 ms 49084 KB Output is correct
7 Correct 154 ms 37244 KB Output is correct
8 Correct 106 ms 35380 KB Output is correct
9 Correct 115 ms 33712 KB Output is correct
10 Correct 103 ms 29504 KB Output is correct
11 Correct 103 ms 30008 KB Output is correct
12 Correct 103 ms 29000 KB Output is correct
13 Correct 103 ms 28992 KB Output is correct
14 Correct 89 ms 27280 KB Output is correct
15 Correct 79 ms 25884 KB Output is correct
16 Correct 47 ms 21588 KB Output is correct
17 Correct 72 ms 29132 KB Output is correct
18 Correct 71 ms 28984 KB Output is correct
19 Correct 76 ms 29356 KB Output is correct
20 Correct 77 ms 29200 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 30192 KB Output is correct
2 Correct 105 ms 30008 KB Output is correct
3 Incorrect 130 ms 29476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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