Submission #674447

#	Time	Username	Problem	Language	Result	Execution time	Memory
674447		Jarif_Rahman	Duathlon (APIO18_duathlon)	C++17	100 / 100	106 ms	33068 KiB

count_triplets

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<vector<int>> graph, tree0;
vector<bool> ap;
vector<int> intime, low;

int N = 0;
vector<vector<int>> tree;
vector<int> bcc, bcc_sz;
vector<int> sz;

ll ans = 0;

int in = 0;
void dfs_ap(int nd, int ss){
    intime[nd] = in++;
    low[nd] = intime[nd];

    for(int x: graph[nd]) if(x != ss){
        if(intime[x] != -1) low[nd] = min(low[nd], intime[x]);
        else{
            tree0[nd].pb(x);
            dfs_ap(x, nd);
            if(low[x] >= intime[nd] && ss != -1) ap[nd] = 1;
            low[nd] = min(low[nd], low[x]);
        }
    }

    if(ss == -1 && tree0[nd].size() > 1) ap[nd] = 1;
}

void dfs_bcc(int nd, int _bcc){
    if(!ap[nd]){
        bcc[nd] = _bcc;
        bcc_sz[_bcc]++;
        for(int x: tree0[nd]) dfs_bcc(x, _bcc);
        return;
    }

    int me = tree.size();
    bcc[nd] = me;
    tree.pb({_bcc});
    bcc_sz.pb(-1);
    tree[_bcc].pb(me);

    for(int x: tree0[nd]){
        if(low[x] >= intime[nd]){
            int __bcc = tree.size();
            tree.pb({me});
            bcc_sz.pb(0);
            tree[me].pb(__bcc);
            dfs_bcc(x, __bcc);
        }
        else dfs_bcc(x, _bcc);
    }
}

void dfs(int nd, int ss){
    sz[nd] = bcc_sz[nd];
    if(sz[nd] == -1) sz[nd] = 1;
    for(int x: tree[nd]) if(x != ss) dfs(x, nd), sz[nd]+=sz[x];
}

int comp_size;
ll dfs2(int nd, int ss, ll X){
    if(bcc_sz[nd] != -1){
        ll s = X;
        for(int x: tree[nd]) if(x != ss) s+=ll(sz[x])*ll(sz[x]-1);
        ans-=s*bcc_sz[nd];
        for(int x: tree[nd]) if(x != ss) dfs2(x, nd, s-ll(sz[x])*ll(sz[x]-1));
        return s-X;
    }
    else{
        ans-=X;
        for(int x: tree[nd]) if(x != ss) ans-=dfs2(x, nd, ll(comp_size-sz[x])*ll(comp_size-sz[x]-1));
        return 0;
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    graph.resize(n);
    tree0.resize(n);
    ap.resize(n, 0);
    intime.resize(n, -1);
    low.resize(n);
    bcc.resize(n);

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

    for(int i = 0; i < n; i++) if(intime[i] == -1){
        dfs_ap(i, -1);

        tree.pb({});
        bcc_sz.pb(0);
        dfs_bcc(i, int(tree.size())-1);
    }

    N = tree.size();
    sz.resize(N, -1);

    for(int i = 0; i < bcc_sz.size(); i++){
        if(sz[i] == -1){
            dfs(i, -1);
            comp_size = sz[i];
            ans+=ll(comp_size)*ll(comp_size-1)*ll(comp_size-2);
            dfs2(i, -1, 0);
        }
    }

    cout << ans << "\n";
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i = 0; i < bcc_sz.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

• 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