Submission #51071

#	Time	Username	Problem	Language	Result	Execution time	Memory
51071		yp155136	Duathlon (APIO18_duathlon)	C++14	0 / 100	355 ms	109908 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];

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

void dfs3(int now,int par)
{
    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 - 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);
        //cout << "ans = " << ans << endl;
    }
    else if (type[now] == 1)
    {
        ;
    }
    for (int i:G2[now])
    {
        if (i != par)
        {
            dfs3(i,now);
        }
    }
}

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;
    }
    dfs(1,1);
    /*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;
            }
        }
    }
    dfs2(vid,vid);
    dfs3(vid,vid);
    printf("%lld\n",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:134: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:138: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: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10