Submission #108752

#	Time	Username	Problem	Language	Result	Execution time	Memory
108752		oolimry	Duathlon (APIO18_duathlon)	C++14	66 / 100	682 ms	76716 KiB

count_triplets

    #include <bits/stdc++.h>
     
    using namespace std;
    int n, m;
    typedef vector<int> vi;
    typedef pair<int,int> ii;
    struct node{
        int depth = -1;
        int low;
        int parent;
        bool vis = false;
        bool isArti = false;
        vi adj;
    };
     
    vector<unordered_set<int> > biconnected;
    stack<int> s; ///this is only needed for biconnected components
    ///note: this will ignore single nodes with no edges
    static node g[200005];
    int rootChildren = 0;
    void dfs(int u){
        if(g[u].depth == -1) g[u].depth = g[g[u].parent].depth + 1;
        g[u].low = g[u].depth;
        g[u].vis = true;
        for(int i = 0;i < g[u].adj.size();i++){
            int v = g[u].adj[i];
            if(!g[v].vis){
                g[v].parent = u;
                if(g[u].depth == 0) rootChildren++;
                s.push(u); ///s traces the path of tree traversal
                dfs(v);
                g[u].low = min(g[u].low,g[v].low);
     
                if(g[v].low >= g[u].depth){
                    g[u].isArti = true;
                    g[u].low = min(g[u].low,g[v].low);
                    unordered_set<int> newSet;
                    int nn;
                    biconnected.push_back(newSet); ///create new biconnected component
                    do{
                        assert(!s.empty());
                        nn = s.top();
                        s.pop();
                        biconnected.back().insert(nn);
                    }while(nn != u);
                }
                ///if(g[v].low > g[u].depth{
                      ///u,v is a bridge
                ///}
            }
            else if(v != g[u].parent){
                g[u].low = min(g[u].low,g[v].low);
            }
            s.push(u);
        }
    }
    struct node2{
        long long sz;
        long long dp = 0;
        bool isArti = false;
        bool vis = false;
        int r;
        int p = -1;
        vi adj;
    };
     
    vector<node2> bct; ///block-cut tree
    long long root = -1;
    void dp(int u){
        if(bct[u].vis) return;
        bct[u].vis = true;
        bct[u].dp = bct[u].sz;
        bct[u].r = root;
        for(int i = 0;i < bct[u].adj.size();i++){
            int v = bct[u].adj[i];
            if(bct[v].vis) continue;
            bct[v].p = u;
            dp(v);
            bct[u].dp += bct[v].dp;
        }
    }
    int main()
    {
        //freopen("i.txt","r",stdin);
        cin >> n >> m;
        ii edges[m];
        for(int i = 0;i < m;i++){
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            g[a].adj.push_back(b);
            g[b].adj.push_back(a);
            edges[i] = ii(a,b);
        }
     
        for(int i = 0;i < n;i++){
            if(!g[i].vis){
                rootChildren = 0;
                g[i].depth = 0;
                dfs(i);
                if(rootChildren > 1) g[i].isArti = true;
                else g[i].isArti = false; ///this line is needed
            }
        }
        unordered_map<int,int> artis;
        for(int i = 0;i < n;i++){
            if(g[i].isArti){
                artis[i] = bct.size();
                node2 nn;
                nn.sz = 1;
                nn.isArti = true;
                bct.push_back(nn);
            }
        }
     
     
        for(int i = 0;i < biconnected.size();i++){
            node2 nn;
            nn.sz = biconnected[i].size();
            nn.isArti = false;
            for(unordered_set<int>::iterator it = biconnected[i].begin();it != biconnected[i].end();it++){
                //cout << *it << " ";
                if(artis.find(*it) != artis.end()){
                    nn.adj.push_back(artis[*it]);
                    bct[artis[*it]].adj.push_back(bct.size());
                    nn.sz--;
                }
            }
            bct.push_back(nn);
            //cout << "\n";
        }
        for(int i = 0;i < bct.size();i++){
            root = i;
            dp(i);
        }
        set<long long> checl;
     
        for(int i = 0;i < bct.size();i++){
            //cout << i << " " << bct[i].sz << " " << bct[i].dp << " " << bct[i].isArti << "| ";
            for(int j = 0;j < bct[i].adj.size();j++){
                //cout << bct[i].adj[j] << " ";
                long long q = i * 1000000000ll + j;
                if(checl.find(q) != checl.end()) assert(false);
                else checl.insert(q);
            }
            //cout << "\n";
        }
     
        long long ans = 0ll;
        for(int i = 0;i < bct.size();i++){
            vector<long long> branches;
            vector<long long> branchStart;
            long long total = 0ll;
            for(int j = 0;j < bct[i].adj.size();j++){
                if(bct[i].adj[j] != bct[i].p){
                    branches.push_back(bct[bct[i].adj[j]].dp);
                    branchStart.push_back(bct[bct[i].adj[j]].sz);
                }
            }
            if(bct[i].p >= 0){
                branches.push_back(bct[bct[i].r].dp - bct[i].dp);
                branchStart.push_back(bct[bct[i].p].sz);
            }
            for(int j = 0;j < branches.size();j++) total += branches[j];
            /*
            long long extra = 0, extra2 = 0;
            if(!bct[i].isArti) extra = max(0ll,(long long)(bct[i].adj.size())-2);
            if(!bct[i].isArti) extra2 = max(0ll,(long long)(bct[i].adj.size())-1);
            for(int j = 0;j < branches.size();j++){
                //cout << i << " " << branches[j] << "\n";
                ///branch1 to self or neighbor articulation point to branch2
                ans += branches[j] * (total - branches[j]) * (bct[i].sz + extra);
     
                ///branch to self to self or self to self to branch
                ans += 2 * (bct[i].sz) * (bct[i].sz + extra2 - 1) * branches[j];
     
                ///self to arti to another branch
                //if(!bct[i].isArti){
                //    ans += 2ll * (bct[i].sz) * branches[j] * (bct[i].adj.size() - 1);
                //}
     
                if(bct[i].isArti){
                    ///direct branch to self to same branch(not reverse) or its reverse
                    ans += 2ll * bct[i].sz * branchStart[j] * (branches[j] - branchStart[j]);
                    ///direct branch to self to direct or its reverse
                    ans += bct[i].sz * (branchStart[j]) * (branchStart[j] - 1);
     
                }
            }
     
     
            ///self to self to self
            ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].sz - 2);
            */
     
            long long sz = bct[i].sz;
            assert(sz >= 0);
            if(!bct[i].isArti){
                ans += sz * (sz - 1) * (sz + bct[i].adj.size() - 2);
                ans += 2ll * sz * (sz + bct[i].adj.size() - 2) * total;
            }
            long long others = bct[bct[i].r].dp - bct[i].dp;
            for(int j = 0;j < bct[i].adj.size();j++){
                int v = bct[i].adj[j];
                if(v != bct[i].p){
                    long long extra = 0;
                    if(!bct[i].isArti) extra = bct[i].adj.size()-2;
                    ans += 2ll * (bct[i].sz + extra) * bct[v].dp * others;
                    others += bct[v].dp;
                }
            }
     
     
            //if(!bct[i].isArti) ans += (bct[i].sz) * (bct[i].sz - 1) * (bct[i].adj.size());
            //cout << i << " " << ans << "\n";
        }
        cout << ans;
    }
     
    /*
    8 7
    8 5
    8 1
    7 5
    8 6
    3 1
    3 2
    8 3
    */
    /*
    10 12
    6 4
    10 3
    4 2
    4 1
    4 3
    6 5
    9 1
    9 4
    2 1
    9 3
    8 5
    7 2
    */

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:25:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < g[u].adj.size();i++){
                       ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dp(int)':
count_triplets.cpp:74:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct[u].adj.size();i++){
                       ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:118:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < biconnected.size();i++){
                       ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:133:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:139:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:141:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < bct[i].adj.size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:151:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < bct.size();i++){
                       ~~^~~~~~~~~~~~
count_triplets.cpp:155:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < bct[i].adj.size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~
count_triplets.cpp:165:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < branches.size();j++) total += branches[j];
                           ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:204:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < bct[i].adj.size();j++){
                           ~~^~~~~~~~~~~~~~~~~~~

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