Submission #363895

#	Time	Username	Problem	Language	Result	Execution time	Memory
363895		doowey	Duathlon (APIO18_duathlon)	C++14	100 / 100	227 ms	30600 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 100;
vector<int> T[N];
vector<int> G[N];

int cnt;
int n;

void add_ver(int c, int u){
    G[c].push_back(u);
    G[u].push_back(c);
}

int tin[N];
int low[N];
bool vis[N];
int ti = 0;

void dfs(int u, int pp){
    vis[u]=true;
    ti ++ ;
    tin[u] = ti;
    low[u] = ti;
    for(auto x : T[u]){
        if(x == pp) continue;
        if(!vis[x]){
            dfs(x,u);
            low[u]=min(low[u],low[x]);
        }
        else{
            low[u]=min(low[u],tin[x]);
        }
    }
}

void dfs1(int u, int bel, int par){
    vis[u]=true;
    for(auto x : T[u]){
        if(!vis[x]){
            int nw = bel;
            if(tin[u] <= low[x]){
                cnt ++ ;
                nw = cnt;
            }
            add_ver(nw, u);
            add_ver(nw, x);
            dfs1(x, nw, u);
        }
    }
}

int sub[N];

void dfs_nw(int u, int pi){
    sub[u] = (u <= n);
    for(auto x : G[u]){
        if(x != pi){
            dfs_nw(x, u);
            sub[u] += sub[x];
        }
    }
}

int total;

ll soln = 0;

void dfs_cc(int u, int pi){
    for(auto x : G[u]){
        if(x != pi){
            dfs_cc(x, u);
        }
    }
    if(u > n){
        int nx;
        int deg = G[u].size();
        for(auto x : G[u]){
            if(x == pi){
               nx = total - sub[u];
            }
            else{
                nx = sub[x];
            }
            soln -= nx * 1ll * (deg - 1) * 1ll * (nx - 1);
        }
    }
}


int main(){
    fastIO;
    int m;
    cin >> n >> m;
    int u, v;
    for(int i = 1; i <= m ; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    for(int i = 1; i <= n; i ++ ){
        if(!vis[i]){
            dfs(i,-1);
        }
    }
    for(int i = 1; i <= n; i ++ ){
        vis[i]=false;
    }
    cnt = n;
    for(int i = 1; i <= n; i ++ ){
        if(!vis[i]){
            dfs1(i, -1, -1);
        }
    }
    for(int i = 1; i <= cnt ;i  ++ ){
        sort(G[i].begin(), G[i].end());
        G[i].resize(unique(G[i].begin(), G[i].end()) - G[i].begin());
    }
    for(int i = 1; i <= n; i ++ ){
        if(sub[i] == 0){
            dfs_nw(i,-1);
            total = sub[i];
            soln += total * 1ll * (total - 1) * 1ll * (total - 2);
            dfs_cc(i,-1);
        }
    }
    cout << soln << "\n";
    return 0;
}

• 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