Submission #51095

#	Time	Username	Problem	Language	Result	Execution time	Memory
51095		yp155136	Duathlon (APIO18_duathlon)	C++14	31 / 100	481 ms	126720 KiB

count_triplets

#include <bits/stdc++.h>
using namespace std;

const int N = 800006;

int e[N];
vector<int> G[N];

int dfn_clock[N];

int stamp=0;

bool vis[N];
int low[N];
stack<int> sta;

vector<int> bcc[N];
vector<int> vv[N];
int bcc_no = 0;

void dfs(int now,int par)
{
    //cout << "now = " << now << " , par = " << par <<endl;
    dfn_clock[now] = low[now] = (++stamp);
    vis[now] = true;
    for (int i:G[now])
    {
        int to = (e[i]^now);
        if (to == par) continue;
        if (!vis[to])
        {
            sta.push(i);
            dfs(to,now);
            low[now] = min(low[now],low[to]);
            if (low[to] >= dfn_clock[now])
            {
                bcc_no++;
                int p;
                do {
                    p = sta.top();
                    bcc[bcc_no].push_back(p);
                    sta.pop();
                } while (p != i);
            }
        }
        else if (dfn_clock[to] < dfn_clock[now])
        {
            sta.push(i);
            low[now] = min(low[now],dfn_clock[to]);
        }
    }
}

typedef long long LL;

LL ans=0;

int cnt[N];
int in_bcc[N];
int type[N];
int sz[N];
int n,m;

int vis2[N];
int vis_id = 880301;

int xx[N],yy[N];

vector<int> G2[N];

int subtree_sz[N];

int n_cid[N];

void dfs2(int now,int par,int cid)
{
    vis[now] = true;
    subtree_sz[now] = sz[now];
    for (int i:G2[now])
    {
        if(i != par)
        {
            dfs2(i,now,cid);
            subtree_sz[now] += subtree_sz[i];
        }
    }
    if (now == par)
    {
        n_cid[cid] = subtree_sz[now];
    }
}

LL tott1[N],tott2[N];

void dfs4(int now,int par,int cid)
{
    vis[now] = true;
    if (type[now] == 1)
    {
        vector<int> szz;
        for (int i:G2[now])
        {
            if (subtree_sz[i] >= subtree_sz[now])
            {
                szz.push_back(n_cid[cid] - subtree_sz[now]);
            }
            else
            {
                szz.push_back(subtree_sz[i]);
            }
        }
        LL tot=0,tot2=0;
        //cout << "now = " << now << " : ";
        for (int i:szz)
        {
            tot += i;
            tot2 += i*1LL*i;
            //cout << i << " ";
        }
        //cout<<endl;
        tott1[now] = tot;
        tott2[now] = tot2;
    }
    for (int i:G2[now])
    {
        if (i != par)
        {
            dfs4(i,now,cid);
        }
    }
}

void dfs3(int now,int par,int cid)
{
    //cout << "now = " << now << " , par = " << par << endl;
    vis[now] = true;
    if (type[now] == 2)
    {
        //cout << "now = " << now << endl;
        //cut vertex
        for (int i:G2[now])
        {
            ans += (sz[i]*1LL*(sz[i]-1));
            //cout << "ans = " << ans << endl;
        }
        //two different
        vector<int> szz;
        for (int i:G2[now])
        {
            if (subtree_sz[i] >= subtree_sz[now])
            {
                szz.push_back(n_cid[cid] - subtree_sz[now]);
            }
            else
            {
                szz.push_back(subtree_sz[i]);
            }
        }
        LL tot=0,tot2=0;
        for (int i:szz)
        {
            tot += i;
            tot2 += i*1LL*i;
        }
        ans += (tot*tot-tot2);
        /*for (int i:G2[now])
        {
            int del_sz = -1;
            assert(type[i] == 1);
            if (subtree_sz[i] >= subtree_sz[now])
            {
                del_sz = subtree_sz[now];
            }
            else
            {
                del_sz = (n_cid[cid] - subtree_sz[i]);
            }
            LL tot1 = tott1[i] - del_sz;
            LL tot2 = tott2[i] - del_sz*1LL*del_sz;
            ans += (tot1*tot1) - tot2;
            //cout << "i = " << i << " , now = "<< now << " , del_sz = " << del_sz << " , tmp = " << (tot1*tot1) - tot2 << endl;
        }*/
        //cout << "ans = " << ans << endl;
    }
    else if (type[now] == 1)
    {
        //cout << "now = " << now << " , sz = " << sz[now] << " , n = " << n_cid[cid] << endl;
        ans += (sz[now]*1LL*(sz[now]-1)*1LL*(sz[now]-2));
        ans += 2*(sz[now]*1LL*(sz[now]-1)*1LL*(n_cid[cid]-sz[now]));
        vector<int> szz;
        for (int i:G2[now])
        {
            if (subtree_sz[i] >= subtree_sz[now])
            {
                szz.push_back(n_cid[cid] - subtree_sz[now]);
            }
            else
            {
                szz.push_back(subtree_sz[i]);
            }
        }
        LL tot=0,tot2=0;
        for (int i:szz)
        {
            tot += i;
            tot2 += i*1LL*i;
        }
        ans += sz[now]*(tot*tot-tot2);
    }
    for (int i:G2[now])
    {
        if (i != par)
        {
            dfs3(i,now,cid);
        }
    }
}

int main ()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        e[i] = (x^y);
        G[x].push_back(i);
        G[y].push_back(i);
        xx[i] = x;
        yy[i] = y;
    }
    for (int i=1;i<=n;++i)
    {
        if (!vis[i])
        {
            dfs(i,i);
        }
    }
    /*for (int i=1;bcc_no>=i;i++)
    {
        cout << "i = " << i << " : ";
        for (int j:bcc[i]) cout << j << ' ';
        cout << endl;
    }*/
    for (int i=1;i<=bcc_no;++i)
    {
        ++vis_id;
        vector<int> v;
        for (int j:bcc[i])
        {
            if (vis2[ xx[j] ] != vis_id)
            {
                v.push_back(xx[j]);
                vis2[ xx[j] ] = vis_id;
            }
            if (vis2[ yy[j] ] != vis_id)
            {
                v.push_back(yy[j]);
                vis2[ yy[j] ] = vis_id;
            }
        }
        for (int j:v)
        {
            cnt[j]++;
        }
        vv[i] = v;
    }
    int vid = n;
    for (int i=1;i<=bcc_no;++i)
    {
        ++vid;
        type[vid] = 1;
        for (int j:vv[i])
        {
            if (cnt[j] == 1)
            {
                sz[vid]++;
            }
            else
            {
                G2[vid].push_back(j);
                G2[j].push_back(vid);
                type[j] = 2;
                sz[j] = 1;
            }
        }
    }
    int cid=0;
    memset(vis,0,sizeof(vis));
    for (int i=n+1;i <= vid;++i)
    {
        if (!vis[i])
        {
            dfs2(i,i,++cid);
        }
    }
    memset(vis,0,sizeof(vis));
    cid=0;
    for (int i=n+1;i<=vid;++i)
    {
        if (!vis[i])
        {
            dfs4(i,i,++cid);
        }
    }
    memset(vis,0,sizeof(vis));
    cid=0;
    for (int i=n+1;i<=vid;++i)
    {
        if (!vis[i])
        {
            dfs3(i,i,++cid);
        }
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:221: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:225:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~

• 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