oj.uz

Submission #1094594

# Submission time Handle Problem Language Result Execution time Memory
1094594 2024-09-30T04:36:25 Z flying_saucer Duathlon (APIO18_duathlon) C++14
0 / 100
 52 ms 42960 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,long long> PLL;
typedef long long LL;

#define ln '\n'
#define faster {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}

#define all(v) v.begin(),v.end()

int mod = 998244353;
const int N = 4e5 + 10;
const int inf = 1e9;

bitset <N> art, good;
vector <int> g[N], tree[N], st, comp[N];
int n, m, ptr, cur, in[N], low[N], id[N];

void dfs (int u, int from = -1) {
  in[u] = low[u] = ++ptr;
  st.emplace_back(u);
  for (int v : g[u]) if (v ^ from) {
    if (!in[v]) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] >= in[u]) {
        art[u] = in[u] > 1 or in[v] > 2;
        comp[++cur].emplace_back(u);
        while (comp[cur].back() ^ v) {
          comp[cur].emplace_back(st.back());
          st.pop_back();
        }
      } 
    } else {
      low[u] = min(low[u], in[v]);
    }
  }
}

void buildTree(int n) {
  ptr = 0;
  for (int i = 1; i <= n; ++i) {
    if (art[i]) id[i] = ++ptr;
  }
  for (int i = 1; i <= cur; ++i) {
    int x = ++ptr;
    for (int u : comp[i]) {
      if (art[u]) {
        tree[x].emplace_back(id[u]);
        tree[id[u]].emplace_back(x);
      } else {
        id[u] = x;
      }
    }
  }
}

void solve(int test){
    int n, m, q; cin>>n>>m;
    for(int i = 0, u, v; i < m; i++){
        cin>>u>>v;
        g[u].push_back(v); g[v].push_back(u);
    }
    dfs(1);
    auto nC2 = [&](LL n){
        return n * (n - 1) / 2;
    };
    auto nC3 = [&](LL n){
        return n * (n - 1) * (n - 2) / 6;
    };
    LL ans = nC3(n);
    for(int i = 1; i <= cur; i++){
        int sz = comp[i].size();
        int artP = 0;
        for(int j = 0; j < sz; j++)
            artP += art[comp[i][j]];
        LL tmp = nC3(sz) * 2 + nC2(sz - 1) * (n - sz);
        ans += tmp;
    }
    cout<<ans * 2<<'\n';
}

signed main(){
    faster
    int t = 1; 
    // cin>>t;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void solve(int)':
count_triplets.cpp:61:15: warning: unused variable 'q' [-Wunused-variable]
   61 |     int n, m, q; cin>>n>>m;
      |               ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 42956 KB Output is correct
2 Correct 45 ms 42960 KB Output is correct
3 Incorrect 40 ms 37712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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