oj.uz

Submission #850278

# Submission time Handle Problem Language Result Execution time Memory
850278 2023-09-16T09:20:28 Z tvladm2009 Duathlon (APIO18_duathlon) C++17
0 / 100
 140 ms 100952 KB 
#include <bits/stdc++.h>
#define int ll

using namespace std;

typedef long long ll;

const int N = (int)3e5 + 7;
int n;
int m;
vector<int> g[N];
vector<int> g2[N];
int dep[N];
int mindep[N];
vector<vector<int>> all;
vector<pair<int, int>> stk;
int dim;
int inside[N];

void dfs(int a) {
  mindep[a] = dep[a];

  for (auto &b : g[a]) {
    if (dep[b] == -1) {
      dep[b] = dep[a] + 1;
      stk.push_back({a, b});
      dfs(b);
      mindep[a] = min(mindep[a], mindep[b]);
      if (mindep[b] >= dep[a]) {
        vector<int> cur;
        while (1) {
          assert(!stk.empty());
          auto it = stk.back();
          cur.push_back(it.first);
          cur.push_back(it.second);
          stk.pop_back();
          if (it == make_pair(a, b)) {
            break;
          }
        }
        sort(cur.begin(), cur.end());
        cur.resize(unique(cur.begin(), cur.end()) - cur.begin());
        all.push_back(cur);

        dim++;
        for (auto &v : cur) {
          inside[dim]++;
          g2[v].push_back(dim);
          g2[dim].push_back(v);
        }
      }
    } else {
      if (dep[b] < dep[a] - 1) {
        mindep[a] = min(mindep[a], dep[b]);
      }
    }
  }
}

int sub[N];
int ninit;
int total = 0;

ll sol = 0;

void solve(int a) {
  sub[a] = (a <= ninit);
  vector<int> kids;
  for (auto &b : g[a]) {
    if (sub[b] == -1) {
      solve(b);
      sub[a] += sub[b];
      kids.push_back(b);
    }
  }
  g[a] = kids;
}

int solve2(int a, int p = -1) {
  for (auto &b : g[a]) {
    solve2(b, a);
    if (a > ninit) {
      sol -= 1LL * (inside[a] - 1) * sub[b] * (sub[b] - 1);
    }
  }
  if (a > ninit) {
    sol -= 1LL * (inside[a] - 1) * (total - sub[a]) * (total - sub[a] - 1);
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
    sub[a] = -1;
  }
  for (int i = 1; i <= n; i++) {
    dep[i] = -1;
  }
  ninit = n;
  dim = n;
  for (int i = 1; i <= n; i++) {
    if (dep[i] == -1) {
      dep[i] = 0;
      dfs(i);
      assert(stk.empty());
    }
  }

  n = dim;
  for (int i = 1; i <= n; i++) {
    g[i] = g2[i];
    sub[i] = -1;
  }

  for (int i = 1; i <= n; i++) {
    if (sub[i] == -1) {
      solve(i);
      total = sub[i];
      sol += 1LL * total * (total - 1) * (total - 2);
      solve2(i);
    }
  }
  cout << sol << "\n";
  return 0;
}

Compilation message

count_triplets.cpp: In function 'll solve2(ll, ll)':
count_triplets.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
   89 | }
      | ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 43540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 43540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 100952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 43996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 87020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 43952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 87036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 43540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 43540 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -