Submission #674358

#	Time	Username	Problem	Language	Result	Execution time	Memory
674358		Jarif_Rahman	Duathlon (APIO18_duathlon)	C++17	31 / 100	102 ms	33908 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;
void dfs2(int nd, int ss){
    ll X = bcc_sz[nd];
    if(X == -1) X = 1;
    if(X >= 2) ans+=X*(X-1)*(comp_size-X)*2;

    for(int x: tree[nd]) if(x != ss) dfs2(x, nd);

    ans+=ll(comp_size-sz[nd])*X*ll(sz[nd]-X);
    for(int x: tree[nd]) if(x != ss){
        ans+=X*ll(sz[x])*ll(comp_size-sz[x]-X);
    }
    if(bcc_sz[nd] == -1){
        if(ss != -1) ans+=ll(comp_size-sz[nd]-bcc_sz[ss])*X*ll(bcc_sz[ss])*2;
        for(int x: tree[nd]) if(x != ss){
            ans+=X*ll(bcc_sz[x])*(sz[x]-bcc_sz[x])*2;
        }
    }
}


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(auto x: ap) cerr << x << " "; cerr << "ap\n";
    for(int x: bcc) cerr << x << " "; cerr << "bcc\n";
    for(int x: bcc_sz) cerr << x << " "; cerr << "bcc_sz\n";
    for(int i = 0; i < N; i++){
        for(int x: tree[i]) if(x > i) cerr << i << " " << x << "\n";
    }*/

    for(int i = 0; i < bcc_sz.size(); i++){
        ll X = bcc_sz[i], c = tree[i].size();
        if(X >= 3) ans+=X*(X-1)*(X-2);
        if(X >= 2) ans+=X*(X-1)*c;

        if(sz[i] == -1){
            dfs(i, -1);
            comp_size = sz[i];
            dfs2(i, -1);
        }
    }

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

Compilation message (stderr)

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

• 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