oj.uz

Submission #1094600

# Submission time Handle Problem Language Result Execution time Memory
1094600 2024-09-30T05:25:10 Z flying_saucer Duathlon (APIO18_duathlon) C++14
8 / 100
 66 ms 38140 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define int long long
#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;


vector<PLL> g[N];
vector<int> comp[N];
int disc[N], low[N], mark[N], vis[N], timer = 1, cur = 1;
vector<int> currcomp;

void dfs(int u, int p){
    disc[u] = low[u] = timer++; currcomp.push_back(u);
    bool fl = 1;
    for(auto [v, id]: g[u]){
        if(v == p && fl) {fl = 0; continue;}
        if(disc[v]){
            low[u] = min(low[u], disc[v]);
        }else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(disc[u] < low[v]){
                mark[id] = 1;
            }
        }
    }
}

void colorComponents(int u, int color){
    if(vis[u]) return;
    comp[color].push_back(u);
    vis[u] = color;
    for(auto [v, id]: g[u]){
        if(mark[id]) continue;
        colorComponents(v, color);
    }
}

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, i}); g[v].push_back({u, i});
    }

    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(!disc[i]){
            dfs(i, -1);
            int SZ = currcomp.size(), last = cur;
            ans += nC3(SZ);
            for(auto u: currcomp){
                if(!vis[u]){
                    colorComponents(u, cur++);
                }
            }
            currcomp.clear();
            for(int j = last; j < cur; j++){
                int sz = comp[j].size(); //cout<<sz<<'\n';
                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 dfs(long long int, long long int)':
count_triplets.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto [v, id]: g[u]){
      |              ^
count_triplets.cpp: In function 'void colorComponents(long long int, long long int)':
count_triplets.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [v, id]: g[u]){
      |              ^
count_triplets.cpp: In function 'void solve(long long int)':
count_triplets.cpp:52:15: warning: unused variable 'q' [-Wunused-variable]
   52 |     int n, m, q; cin>>n>>m;
      |               ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19272 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 8 ms 19272 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 8 ms 19216 KB Output is correct
7 Incorrect 9 ms 19208 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19272 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 8 ms 19272 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 8 ms 19216 KB Output is correct
7 Incorrect 9 ms 19208 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 63 ms 38140 KB Output is correct
2 Correct 55 ms 38084 KB Output is correct
3 Correct 66 ms 34896 KB Output is correct
4 Correct 56 ms 37324 KB Output is correct
5 Correct 52 ms 32896 KB Output is correct
6 Correct 53 ms 33624 KB Output is correct
7 Correct 57 ms 32600 KB Output is correct
8 Correct 54 ms 33492 KB Output is correct
9 Correct 48 ms 31624 KB Output is correct
10 Correct 55 ms 32112 KB Output is correct
11 Correct 38 ms 29904 KB Output is correct
12 Correct 39 ms 30040 KB Output is correct
13 Correct 41 ms 29532 KB Output is correct
14 Correct 36 ms 29276 KB Output is correct
15 Correct 30 ms 28508 KB Output is correct
16 Correct 31 ms 28392 KB Output is correct
17 Correct 14 ms 24676 KB Output is correct
18 Correct 13 ms 24740 KB Output is correct
19 Correct 13 ms 24676 KB Output is correct
20 Correct 13 ms 24596 KB Output is correct
21 Correct 13 ms 24668 KB Output is correct
22 Correct 13 ms 24668 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19272 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 8 ms 19272 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 8 ms 19216 KB Output is correct
7 Incorrect 9 ms 19208 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 19032 KB Output is correct
2 Correct 8 ms 19272 KB Output is correct
3 Correct 8 ms 19032 KB Output is correct
4 Correct 8 ms 19272 KB Output is correct
5 Correct 7 ms 19032 KB Output is correct
6 Correct 8 ms 19216 KB Output is correct
7 Incorrect 9 ms 19208 KB Output isn't correct
8 Halted 0 ms 0 KB -