Submission #563444

#	Time	Username	Problem	Language	Result	Execution time	Memory
563444		khangal	Duathlon (APIO18_duathlon)	C++14	23 / 100	161 ms	78832 KiB

count_triplets

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long, long long > pl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18    
#define MIN -1e18
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll N , n, m, mid, res,pos, mn, mx, sum, h1, h2, arr[3234567],arr1[1234567],k, i, j, h, a, x, y, z,par[1234567],ans;
bool used[1234567];
ll tp[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
//ll jump[22][223456];
//ll lvl[1234567];
//ll bit[1234567];
//ll timer;
//ll st[1234567],endd[1234567];
//ll dp[5005][5005];
vl edge[1234567],bcc_graph[1234567],stck;
ll low[1234567] , timer=0 , disc[1234567],bccs=1;
void dfs1(ll node,ll par=0){
    low[node] = disc[node] = timer++;
    //set timer
    stck.pb(node);
    N++;
    for(auto u:edge[node]){
        if(u!=par){
            if(disc[u]){
                low[node] = min(low[node] , disc[u]);
                //find low
            }
            else{
                dfs1(u,node);
                low[node] = min(low[node] , low[u]);
                if(low[u] >= disc[node]){
                    //here is articular point
                    //connect edge
                    bcc_graph[node].pb(n+bccs);
                    //make biconnected graph
                    while(!bcc_graph[n+bccs].size() || bcc_graph[n+bccs].back()!=u){
                        bcc_graph[n+bccs].pb(stck.back());
                        stck.pop_back();
                    }
                    bccs++;
                }
            }
        }
    }
}
ll sz[1234567];
void dfs2(ll node){
    //cout<<node<<'\n';
    sz[node] = (node<=n);
    for(auto u:bcc_graph[node]){
        dfs2(u);
        sz[node]+=sz[u];
        if(node > n){
            ans -= bcc_graph[node].size()*(sz[u])*(sz[u]-1);
        }
    }
    if(node>n){
        ans-= bcc_graph[node].size()*(N-sz[node])*(N-sz[node]-1);
    }
}
class A {  
public :
    static void funcA() {
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            edge[x].pb(y);
            edge[y].pb(x);
        }
        for(int i=1;i<=n;i++){
            if(disc[i]==0){
                N=0;
                dfs1(i);
                ans += N*(N-1)*(N-2);
                dfs2(i);
            }
        }
        cout<<ans;
    }
}lol;
void solve() {
    A::funcA();
}
int main() {
    ll T = 1;
    //cin>>T;
    boost;
    while (T--) {   
        solve();
    }
}
    

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