Submission #57582

#	Time	Username	Problem	Language	Result	Execution time	Memory
57582		Crown	Duathlon (APIO18_duathlon)	C++14	31 / 100	393 ms	78844 KiB

count_triplets

//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int maxn = 1e5+5;
const int maxm = 2e5+5;
vii adj[maxn];
int a[maxm];
int b[maxm];
int num[maxn];
bool art[maxn];
int sz[maxm+maxn];
int low[maxn];
int col[maxm];
bool instack[maxn];
int comps = 0;
int treecmp[maxm];
int cnt[maxm+maxn];
vi tree[maxm+maxn];
stack<int> S;
int tim = 1;
void dfs(int u, int p)
{
    num[u] = low[u] = tim++;
    int chil = 0;
    for(auto edge : adj[u])
    {
        int v = edge.X, id = edge.Y;
        if(!num[v])
        {
            if(!instack[id])
            {
                instack[id] = true;
                S.push(id);
            }
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            chil++;
            if((p && num[u]<= low[v]) || (!p && chil> 1))
            {
                art[u] = true;
                comps++;
                while(true)
                {
                    int x = S.top(); S.pop();
                    col[x] = comps;
                    if(x == id) break;
                }
            }
        }
        else if(v != p)
        {
            if(!instack[id])
            {
                S.push(id);
                instack[id] = true;
            }
            low[u] = min(low[u], num[v]);
        }
    }
}
ll tot = 0;
int artcnt = 0;
bool pong[maxn+maxm];
void tfs(int u, int p)
{
    pong[u] = true;
    cnt[u] = sz[u];
    for(auto kk : tree[u])
    {
        int v = kk;
        if(v == p) continue;
        tfs(v, u);
        cnt[u] += cnt[v];
    }
}
void find_ans(int u, int p, int prv)
{
    //printf("call %d: %d, %d\n", u, sz[u], prv);
    if(u> comps)
    {
        int now = prv;
        tot += 2LL*sz[p]*(prv-sz[p]);
        tot += 1LL*sz[p]*(sz[p]-1);
        for(auto v : tree[u])
        {
            if(v == p) continue;
            tot += 2LL*now*cnt[v];
            //printf("here %lld\n", tot);
            tot += 2LL*sz[v]*(cnt[v]-sz[v]);
            tot += 1LL*sz[v]*(sz[v]-1);
            now += cnt[v];
        }
    }
    else
    {
        int now = prv;
        for(auto v : tree[u])
        {
            if(v == p) continue;
            tot += 2LL*sz[u]*cnt[v]*now;
            now += cnt[v];
        }
        //printf("tot before is %lld\n", tot);
        tot += 2LL*(sz[u]-1)*sz[u]*now;
        tot += 1LL*(sz[u])*(sz[u]-1)*(sz[u]-2);
    }
    //printf("tot is now %lld\n", tot);
    for(auto v : tree[u]) if(v != p) find_ans(v, u, prv+cnt[u]-cnt[v]);
}
int main()
{
    int n, m; scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; i++)
    {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].pb(ii(v, i));
        adj[v].pb(ii(u, i));
        a[i] = u; b[i] = v;
    }
    for(int i = 1; i<= n; i++)
    {
        if(num[i]) continue;
        dfs(i, 0);
        comps++;
        while(!S.empty())
        {
            int x = S.top(); S.pop();
            col[x] = comps;
        }
    }
    for(int i = 1; i<= n; i++)
    {
        if(art[i])
        {
            artcnt++;
            treecmp[i] = artcnt+comps;
        }
    }
    for(int i = 1; i<= m; i++)
    {
        int u = a[i], v = b[i];
        if(!art[u]) swap(u, v);
        if(!art[u])
        {
            treecmp[u] = treecmp[v] = col[i];
        }
        else
        {
            tree[treecmp[u]].pb(col[i]);
            tree[col[i]].pb(treecmp[u]);
            //printf("connect %d %d\n", treecmp[u], col[i]);
            if(art[v])
            {
                tree[treecmp[v]].pb(col[i]);
                tree[col[i]].pb(treecmp[v]);
                //printf("connect %d %d\n", treecmp[v], col[i]);
            }
            else
            {
                treecmp[v] = col[i];
            }
        }
    }
    for(int i = 1; i<= comps+artcnt; i++)
    {
        sort(tree[i].begin(), tree[i].end());
        tree[i].resize(unique(tree[i].begin(), tree[i].end())-tree[i].begin());
    }
    //printf("%d, %d\n", comps, artcnt);
    for(int i = 1; i<= n; i++) sz[treecmp[i]]++;
    for(int i = 1; i<= comps+artcnt; i++)
    {
        if(pong[i]) continue;
        tfs(i, 0);
        find_ans(i, 0, 0);
    }
    printf("%lld\n",tot);
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:117:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n, m; scanf("%d %d", &n, &m);
               ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:120:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d %d", &u, &v);
                   ~~~~~^~~~~~~~~~~~~~~~~

• 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