Submission #48873

#	Time	Username	Problem	Language	Result	Execution time	Memory
48873		IvanC	Duathlon (APIO18_duathlon)	C++17	31 / 100	303 ms	22380 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> ii;
 
const int MAXN = 1e5 + 10;
 
 
vector<int> grafo[MAXN],tree[MAXN];
vector<ii> pontes;
int block[MAXN],grau[MAXN],sz[MAXN],N,M,dsu_p[MAXN],dsu_tam[MAXN],num[MAXN],low[MAXN],dfsPtr;
ll tot,comp_size;
 
int find(int x){
    if(x == dsu_p[x]) return x;
    return dsu_p[x] = find(dsu_p[x]);
}
 
void join(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(dsu_tam[x] < dsu_tam[y]) swap(x,y);
    dsu_tam[x] += dsu_tam[y];
    dsu_p[y] = x;
}
 
void dfs_bridge(int v,int p){
    num[v] = low[v] = ++dfsPtr;
    for(int u : grafo[v]){
        if(u == p) continue;
        if(num[u] == 0){
            dfs_bridge(u,v);
            if(low[u] > num[v]){
                pontes.push_back(ii(u,v));
            }
            else{
                join(u,v);
            }
            low[v] = min(low[v],low[u]);
        }
        else{
            low[v] = min(low[v],num[u]);
        }
    }
}
 
void dfs_tree_1(int v,int p){
    block[v] = 1;
    sz[v] = dsu_tam[v];
    for(int u : tree[v]){
        if(u == p) continue;
        dfs_tree_1(u,v);
        sz[v] += sz[u];
    }
}
 
void dfs_tree_2(int v,int p){
    tot += 1LL*(dsu_tam[v])*(dsu_tam[v] - 1)*(dsu_tam[v]-2);
    vector<int> filhos;
    for(int u : tree[v]){
        if(u == p) continue;
        filhos.push_back(sz[u]);
        dfs_tree_2(u,v);
    }
    filhos.push_back(comp_size - sz[v]);
    for(int i = 0;i<filhos.size();i++){
        int sub_arvore = filhos[i];
        tot += 1LL*dsu_tam[v]*sub_arvore*(comp_size - sub_arvore - dsu_tam[v]);
        tot += 2LL*sub_arvore*(dsu_tam[v] - 1)*(dsu_tam[v] - 2);
        tot += 2LL*sub_arvore*(dsu_tam[v] - 1);
    }
}
 
int main(){
    scanf("%d %d",&N,&M);
     
    for(int i = 1;i<=N;i++){
        dsu_p[i] = i;
        dsu_tam[i] = 1;
    }
 
    for(int i = 1;i<=M;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        grafo[v].push_back(u);
        grafo[u].push_back(v);
    }
 
    for(int i = 1;i<=N;i++){
        if(num[i] == 0) dfs_bridge(i,-1);
    }
 
    for(int i = 0;i<pontes.size();i++){
        int u = find(pontes[i].first);
        int v = find(pontes[i].second);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
 
    //printf("Pontes %d\n",(int)pontes.size());
 
    for(int i = 1;i<=N;i++){
        if(find(i) != i || block[i]) continue;
        dfs_tree_1(i,-1);
        comp_size = sz[i];
        dfs_tree_2(i,-1);
    }
 
    printf("%lld\n",tot);
 
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs_tree_2(int, int)':
count_triplets.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<filhos.size();i++){
                   ~^~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<pontes.size();i++){
                   ~^~~~~~~~~~~~~~
count_triplets.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&u,&v);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 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