Submission #105472

#	Time	Username	Problem	Language	Result	Execution time	Memory
105472		oolimry	Duathlon (APIO18_duathlon)	C++14	10 / 100	1014 ms	169364 KiB

count_triplets

#include <bits/stdc++.h>

using namespace std;
int n, m;

typedef vector<int> vi;

vi adj[2000005];
int counter;
int num[2000005];
int low[2000005];
int parent[2000005];
int artv[2000005];
int dfsRoot;
int rootChildren;
void dfs(int u){
    low[u] = num[u] = counter++;
    for(int i =0 ;i < adj[u].size();i++){
        int v = adj[u][i];
        if(num[v] == -1){
            parent[v] = u;
            if(u == dfsRoot) rootChildren++;
            dfs(v);
            if(low[v] >= num[u])
                artv[u] = 1;

            low[u] = min(low[u],low[v]);
        }
        else if(v != parent[u]){
            low[u] = min(low[u],num[v]);
        }

    }
}


class UFDS {
typedef vector<int> vi;
public:
    vi p, rak, setSize;
    int numSets;

    void create(int n){
        setSize.assign(n, 1);
        numSets = n;
        rak.assign(n, 0);
        p.assign(n, 0);
        for(int i =0;i < n;i++){
            p[i] = i;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        if(isSameSet(i,j))
            return;
        numSets--;
        int x = findSet(i);
        int y = findSet(j);

        if(rak[x] > rak[y]) {
            p[y] = x; setSize[x] += setSize[y];
        }

        else {
            p[x] = y; setSize[y] += setSize[x];
            if(rak[x] == rak[y]) rak[y]++;
        }

    }
};

struct node{
    long long value;
    vi adj;
    long long childSize;
    bool vis = false;
};
node tree[2000005];
vector<long long> cc;
void dp(long long u){
    if(tree[u].vis) return;
    tree[u].vis = true;
    cc.push_back(u);
    tree[u].childSize = tree[u].value;
    for(long long i = 0;i < tree[u].adj.size();i++){
        long long v = tree[u].adj[i];
        if(tree[v].vis) continue;
        dp(v);
        tree[u].childSize += tree[v].childSize;
    }
}


int main()
{
    //freopen("i.txt","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i = 0;i < m;i++){
        int a, b;
        scanf("%d %d",&a,&b);
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    counter = 0;
    fill(num,num+n,-1);
    fill(low,low+n,0);
    fill(parent,parent+n,0);
    fill(artv,artv+n,0);

    for(int i = 0;i < n;i++){
        if(num[i] == -1){
            dfsRoot = i;
            rootChildren = 0;
            dfs(i);
            artv[i] = (rootChildren > 1);
        }
    }
    bool has = false;

    set<int> articulation;
    for(int i = 0;i < n;i++){
        //cout << artv[i] << "\n";

    }

    UFDS uf;
    uf.create(n);

    for(int i = 0;i < n;i++){
        for(int j = 0;j < adj[i].size();j++){
            int v = adj[i][j];
            if(artv[v] == 0 && artv[i] == 0){
                uf.unionSet(i,v); /// forming the BCCs without the articulation points
            }
        }
    }
    map<int,int> ufParents;
    for(int i = 0;i < n;i++){
        int p = uf.findSet(i);
        if(ufParents.find(p) == ufParents.end()){
            ufParents[p] = 0;
        }
    }
    int c = 0;
    for(map<int,int>::iterator it = ufParents.begin();it != ufParents.end();it++){
        it->second = c;
        tree[c].value = uf.setSize[uf.findSet(it->first)];
        c++;
    }
    typedef pair<int,int> ii;
    set<ii> edges;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < adj[i].size();j++){
            int v = adj[i][j];
            int x = ufParents[uf.findSet(i)];
            int y = ufParents[uf.findSet(v)];
            if(x != y){
                edges.insert(ii(x,y));
                edges.insert(ii(y,x));
            }
        }
    }

    for(ii a : edges){
        tree[a.first].adj.push_back(a.second);
    }
    /*
    for(int i = 0;i < 3;i++){
        cout << i << ": " << tree[i].value << "\n";
        for(int j = 0;j < tree[i].adj.size();j++){
            int v = tree[i].adj[j];
            cout << v << " ";
        }
        cout << "\n";
    }
    */
    long long ans = 0ll;
    for(int i = 0;i < ufParents.size();i++){
        cc.clear();
        if(!tree[i].vis){
            dp(i);
            for(int j = 0;j < cc.size();j++){
                //cout << cc[j] << " ";
                int u = cc[j];
                for(int k = 0;k < tree[u].adj.size();k++){
                    int v = tree[u].adj[k];
                    if(tree[v].childSize > tree[u].childSize) continue;
                    ans += (tree[u].value) * (tree[v].childSize) * (tree[i].childSize - tree[u].value - tree[v].childSize);
                    //cout << tree[u].value << "\n";
                }
                ans += (tree[u].value) * (tree[i].childSize - tree[u].childSize) * (tree[u].childSize - tree[u].value);
                //cout << (tree[u].value) << " " << (tree[i].childSize - tree[u].childSize) << " " << (tree[u].childSize - tree[u].value) << "\n";;
                ans += 2ll * (tree[u].value) * (tree[u].value - 1) * (tree[i].childSize - 2);
                ans += (tree[u].value) * (tree[u].value - 1) * (tree[i].adj.size());
            }
        }
    }


    cout << ans;



    //ans++;
    //printf("%d",ans);
    return 0;
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i =0 ;i < adj[u].size();i++){
                   ~~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dp(long long int)':
count_triplets.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i = 0;i < tree[u].adj.size();i++){
                         ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:140:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < adj[i].size();j++){
                       ~~^~~~~~~~~~~~~~~
count_triplets.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < adj[i].size();j++){
                       ~~^~~~~~~~~~~~~~~
count_triplets.cpp:188:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < ufParents.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp:192:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0;j < cc.size();j++){
                           ~~^~~~~~~~~~~
count_triplets.cpp:195:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k = 0;k < tree[u].adj.size();k++){
                               ~~^~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:128:10: warning: unused variable 'has' [-Wunused-variable]
     bool has = false;
          ^~~
count_triplets.cpp:105: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:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

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