Submission #1309938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309938		KindaGoodGames	Duathlon (APIO18_duathlon)	C++20	0 / 100	118 ms	34752 KiB

count_triplets

#include<bits/stdc++.h>

#define int long long
using namespace std;

int mod = 1e9+7;

vector<vector<int>> comps;
vector<int> num,low,bcc;
int counter = 0;
stack<int> S;

vector<vector<int>> adj;
int original = 0;
vector<bool> isArt;
void Tarjan(int v, int p){
    num[v] = low[v] = counter++;
    S.push(v);
    for(auto u : adj[v]){
        if(u == p) continue;
        if(num[u] == -1){
            Tarjan(u,v);
            low[v] = min(low[v], low[u]);

            if(num[v] <= low[u]){
                isArt[v] = num[v] != original || (num[v] == original && num[u] > original);
                vector<int> c;
                while(c.empty() || c.back() != u){
                    bcc[S.top()] = comps.size();
                    c.push_back(S.top()); S.pop();
                }
                comps.push_back(c);
            }
        }else{
            low[v] = min(low[v], num[u]);
        } 
    }
}

vector<int> sz;
vector<vector<int>> dp(4,vector<int>(4));
int total = 0;

void DFS(int v, int p, vector<bool>& vis, vector<set<int>>& adj){
    vis[v] = true;

    int s = comps[v].size();
    vector<int> subs;
    int tot = 0;
    auto get = [&](int k){
        int p = 0;
        for(int i = 0; i < k; i++){
            p *= s-i;
        }
        return p;
    };
    for(auto u : adj[v]){
        if(u == p) continue;
        DFS(u,v,vis,adj);
        subs.push_back(sz[u]);
        sz[v] += sz[u];
        tot += sz[u];

        for(int k = 1; k <= 3; k++){
            for(int i = 0; i <= k; i++){ 
                dp[k][v] += dp[k-i][u]*get(i);
                dp[k][v] %= mod;
            }
        }
    } 
    int t = subs.size();
    for(int i = 0; i < t; i++){
        for(int j = i+1; j < t; j++){
            for(int a = 0; a <= 3; a++){
                for(int b = 0; a+b <= 3; b++){
                    total += get(3-a-b) * dp[a][i] * dp[b][j];
                    total %= mod;
                }
            }
        }
    }
}

int32_t main(){
    int n,m;
    cin >> n >> m;

    low = num = bcc =vector<int>(n,-1);
    adj.resize(n);
    isArt.resize(n);

    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for(int i = 0; i < n; i++){
        if(num[i] == -1){
            original = i;
            Tarjan(i,i);
        }
    }

    int b = comps.size();
    vector<set<int>> tree(b);
    for(int i = 0; i < n; i++){
        if(isArt[i]){
            tree.push_back({}); 
            comps.push_back({i}); 
            bcc[i] = b++;
        }
    }
    for(int i = 0; i < n; i++){
        if(isArt[i]){ 
            for(auto u : adj[i]){ 
                if(bcc[u] == bcc[i]) continue;
                tree[bcc[i]].insert(bcc[u]);
                tree[bcc[u]].insert(bcc[i]);
            } 
        }
    }

    sz.resize(b);
    vector<bool> vis(b);
    for(int i = 0; i < b; i++){
        if(!vis[i]){
            DFS(i,i,vis,tree);
        }
    }

    cout << total << endl;
}

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