Submission #135032

#	Time	Username	Problem	Language	Result	Execution time	Memory
135032		Lawliet	Duathlon (APIO18_duathlon)	C++14	23 / 100	1105 ms	1048580 KiB

count_triplets

#include <bits/stdc++.h>

#define MAX 100010

using namespace std;
typedef long long int lli;

int n, m;
int n1, n2;

int sub[MAX];
int prof[MAX];

lli ans;

lli sumProf[MAX];
lli ansRoot[MAX];

bool marc[MAX];

vector<int> grafo[MAX];

void DFSCalculate(int i, int p, int depth)
{
	sub[i] = 1;
	marc[i] = true;

	sumProf[i] = depth;

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];

		if(prox == p) continue;

		DFSCalculate(prox , i , depth + 1);

		sub[i] += sub[prox];//SOMA ATÉ RAIZ
		sumProf[i] += sumProf[prox];
	}
}

void DFSRotate(int i, int p)
{
	ansRoot[i] = sumProf[i];

	for(int g = 0 ; g < grafo[i].size() ; g++)
	{
		int prox = grafo[i][g];

		if(prox == p) continue;

		int lastSubI = sub[i];
		int lastSubProx = sub[prox];

		lli lastSumI = sumProf[i];
		lli lastSumProx = sumProf[prox];

		sub[i] -= sub[prox];
		sumProf[i] -= sumProf[prox];

		sumProf[prox] += sumProf[i] + sub[i] - sub[prox];
		sub[prox] += sub[i];

		DFSRotate(prox , i);

		sub[i] = lastSubI;
		sub[prox] = lastSubProx;

		sumProf[i] = lastSumI;
		sumProf[prox] = lastSumProx;
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 0 ; g < m ; g++)
	{
		scanf("%d %d",&n1,&n2);

		grafo[n1].push_back(n2);
		grafo[n2].push_back(n1);
	}

	for(int g = 1 ; g <= n ; g++)
	{
		if(marc[g]) continue;

		DFSCalculate(g , g , 0);
		DFSRotate(g , g);

		lli p = sub[g];
		p *= sub[g] - 1;

		ans -= p;
	}

	for(int g = 1 ; g <= n ; g++)
		ans += ansRoot[g];

	printf("%lld\n",ans);
}

Compilation message (stderr)

count_triplets.cpp: In function 'void DFSCalculate(int, int, int)':
count_triplets.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void DFSRotate(int, int)':
count_triplets.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:77:7: 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:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~

• 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