oj.uz

Submission #1094595

# Submission time Handle Problem Language Result Execution time Memory
1094595 2024-09-30T04:46:11 Z flying_saucer Duathlon (APIO18_duathlon) C++14
8 / 100
 45 ms 43468 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, int &SZ) {
  in[u] = low[u] = ++ptr; SZ++;
  st.emplace_back(u);
  for (int v : g[u]) if (v ^ from) {
    if (!in[v]) {
      dfs(v, u, SZ);
      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);
    }

    auto nC2 = [&](LL n){
        return n * (n - 1) / 2;
    };
    auto nC3 = [&](LL n){
        return n * (n - 1) * (n - 2) / 6;
    };
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        if(!in[i]){
            int SZ = 0, last = cur + 1;
            dfs(i, -1, SZ);
            ans += nC3(SZ);
            for(int j = last; j <= cur; j++){
                int sz = comp[j].size();
                int artP = 0;
                for(int k = 0; k < sz; k++)
                    artP += art[comp[j][k]];
                LL tmp = nC3(sz) * 2 + nC2(sz - 1) * (SZ - 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 Correct 6 ms 29020 KB Output is correct
2 Correct 7 ms 29056 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 6 ms 29016 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Incorrect 5 ms 29020 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 7 ms 29056 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 6 ms 29016 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Incorrect 5 ms 29020 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 44 ms 43468 KB Output is correct
2 Correct 41 ms 43464 KB Output is correct
3 Correct 37 ms 39508 KB Output is correct
4 Correct 41 ms 42956 KB Output is correct
5 Correct 37 ms 38628 KB Output is correct
6 Correct 37 ms 39264 KB Output is correct
7 Correct 45 ms 38244 KB Output is correct
8 Correct 41 ms 39016 KB Output is correct
9 Correct 39 ms 37216 KB Output is correct
10 Correct 35 ms 37680 KB Output is correct
11 Correct 31 ms 35676 KB Output is correct
12 Correct 33 ms 35424 KB Output is correct
13 Correct 37 ms 35424 KB Output is correct
14 Correct 29 ms 35420 KB Output is correct
15 Correct 25 ms 34532 KB Output is correct
16 Correct 24 ms 34268 KB Output is correct
17 Correct 6 ms 30448 KB Output is correct
18 Correct 8 ms 30448 KB Output is correct
19 Correct 8 ms 30448 KB Output is correct
20 Correct 6 ms 30436 KB Output is correct
21 Correct 7 ms 30432 KB Output is correct
22 Correct 8 ms 30428 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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