Submission #59358

#	Time	Username	Problem	Language	Result	Execution time	Memory
59358		MatheusLealV	Duathlon (APIO18_duathlon)	C++17	23 / 100	1138 ms	787188 KiB

count_triplets

#include <bits/stdc++.h>
#define N 100050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll n, m, c, ans, ok[N];
   
vector< pii > grafo[N];

vector< int > G[N];
 
ll sz[N], tot = 0;

int dfsnum[N], dfslow[N], cnt, pai[N], ponte[N];

int superpai[N], tam[N];

vector < pii > A;

void dfs(int x)
{
	dfsnum[x] = dfslow[x] = ++cnt;
 
	for(int i = 0; i< grafo[x].size(); i++)
	{
		int v =grafo[x][i].f, id = grafo[x][i].s;
 
		if(!dfsnum[v])
		{
			pai[v] = x;
 
			dfs(v);
 
			if(dfslow[v] > dfsnum[x]) ponte[id] = 1;
 
			dfslow[x] = min(dfslow[v], dfslow[x]);
		}
 
		else if(v != pai[x]) dfslow[x] = min(dfsnum[v], dfslow[x]);
	}
}

void dfspai(int x, int p)
{
	tam[p] ++;

	superpai[x] = p;

	ok[x] = 1;

	for(auto v: grafo[x])
	{
		if(ok[v.f] or ponte[v.s]) continue;

		dfspai(v.f, p);
	}
}
  
void fill(int x, int p)
{
	tot += tam[x];

	for(auto v: G[x])
	{
		if(v == p) continue;

		fill(v, x);
	}
}

ll F[N];

void dfs2(int x, int p)
{	
	//cout<<x<<" "<<tam[x]<<"\n";

	sz[x] = tam[x];

	ok[x] = 1;

	ll quadrado = 0, soma = 0, prod2 = 0;

	int qtd = 0;

	for(auto v: G[x])
	{
		if(v == p) continue;

		qtd ++;

		dfs2(v, x);

		F[x] += F[v];

		quadrado += sz[v] * sz[v];

		soma += sz[v];

		sz[x] += sz[v];

		if(tam[x] >= 2) prod2 += 2 * sz[v] * ((tam[x] - 1)* (tam[x] - 1));

		prod2 -= (sz[v]) * (F[v] - 1) * (tam[x] - 1);

		//if(tam[x] >= 2) prod2 -= sz[v] * (tam[x] - 1);

		//if(tam[x] >= 2) prod2 += sz[v] * (tam[x] - 1);
	}

	if(tam[x] >= 2) prod2 += 2*(tot - sz[x]) * ((tam[x] - 1)* (tam[x] - 1));

	//prod2 -= (tot - sz[x]) * (sz[x]) * (tam[x] - 1);

	//if(tam[x] >= 2) prod2 -= (tot - sz[x]) * (tam[x] - 1);

	//if(tam[x] >= 2) prod2 += (tot - sz[x]) * (tam[x] - 1);
//	cout<<"OIIII = "<<x<<" resp = "<<(prod2)<<"\n";

	soma += tot - sz[x];

	quadrado += (tot - sz[x]) * (tot - sz[x]);

	prod2 += (soma * soma - quadrado) * tam[x];

	ans += prod2;

	if(qtd == 0)
	{
		if(tam[x] >= 2) prod2 += (tot - sz[x]) * (tam[x] * (tam[x] - 1));

		if(tam[x] >= 2) prod2 -= (tot - sz[x]) * (tam[x] - 1);
	}

	//cout<<"MID = "<<x<<" resp = "<<prod2<<" "<<tot<<" "<<sz[x]<<" "<<tam[x]<<"\n";
}


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
  
    cin>>n>>m;    
  
    for(int i = 1, a, b; i <= m; i++)
    {
        cin>>a>>b;
   
        grafo[a].push_back({b, i});
  
        grafo[b].push_back({a, i});

        A.push_back({a, b});
    }

    for(int i = 1; i <= n; i++) if(!dfsnum[i]) dfs(i);

    for(int i = 1; i <= n; i++) if(!ok[i]) dfspai(i, i);

    for(int i = 0; i < m; i++)
    {
    	int a = A[i].f, b = A[i].s;

    	if(superpai[a] != superpai[b])
    	{
    		G[superpai[a]].push_back(superpai[b]);

    		G[superpai[b]].push_back(superpai[a]);

    		//cout<<"A "<<superpai[a]<<" "<<superpai[b]<<"\n";
    	}
    }

    for(int i = 1; i <= n; i++)
    {
    	if(tam[i] <= 2) continue;

    	ans += (tam[i] * (tam[i] - 1) * (tam[i] - 2));
    }

    memset(ok, 0, sizeof ok);

   // cout<<" ---- \n";

    for(int i = 1; i <= n; i++)
    {
  		if(ok[i]) continue;

		tot = 0;

		fill(i, i);

		dfs2(i, i);
    }

    cout<<ans<<"\n";
}

Compilation message (stderr)

count_triplets.cpp: In function 'void dfs(int)':
count_triplets.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i< grafo[x].size(); i++)
                 ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 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