Submission #1160012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160012		SmuggingSpun	Duathlon (APIO18_duathlon)	C++17	100 / 100	60 ms	26948 KiB

count_triplets

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
const int lim = 1e5 + 5;
int n, m, N, cnt_bcc = 0, time_dfs = 0, low[lim], num[lim], cnt[lim << 1];
ll ans = 0;
stack<int>stk;
vector<int>g[lim], bcc_g[lim << 1];
void dfs_1(int s, int p = -1){
    low[s] = num[s] = ++time_dfs;
    stk.push(s);
    N++;
    for(int& d : g[s]){
        if(d != p){
            if(num[d] == 0){
                dfs_1(d, s);
                minimize(low[s], low[d]);
                if(low[d] >= num[s]){
                    bcc_g[s].emplace_back(++cnt_bcc + n);
                    while(stk.top() != d){
                        bcc_g[cnt_bcc + n].emplace_back(stk.top());
                        stk.pop();
                    }
                    bcc_g[cnt_bcc + n].emplace_back(d);
                    stk.pop();
                }
            }
            else{
                minimize(low[s], num[d]);
            }
        }
    }
}
void dfs_2(int s){
    cnt[s] = int(s <= n);
    for(int& d : bcc_g[s]){
        dfs_2(d);
        cnt[s] += cnt[d];
        if(s > n){
            //cout << s << " " << d << " " << cnt[d] << " " << bcc_g[s].size() << " | " <<  1LL * bcc_g[s].size() * cnt[d] * (cnt[d] - 1) << endl;
            ans -= 1LL * bcc_g[s].size() * cnt[d] * (cnt[d] - 1);
        }
    }
    if(s > n){
        ans -= 1LL * bcc_g[s].size() * (N - cnt[s]) * (N - cnt[s] - 1);
    }    
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    memset(num, 0, sizeof(num));
    for(int i = 1; i <= n; i++){
        if(num[i] == 0){
            N = 0;
            dfs_1(i);
            ans += 1LL * N * (N - 1) * (N - 2);
            dfs_2(i);
        }
    }
    cout << ans;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10