Submission #135039

#	Time	Username	Problem	Language	Result	Execution time	Memory
135039		Lawliet	Duathlon (APIO18_duathlon)	C++14	8 / 100	90 ms	12272 KiB

count_triplets

#include <bits/stdc++.h>

#define MAX 100010

using namespace std;
typedef long long int lli;

int n, m;
int n1, n2;

lli ans;

int ingrau[MAX];

bool marc[MAX];

vector<int> grafo[MAX];

bool DFS(int i, int p, int& sz)
{
	marc[i] = true;

	sz++;

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

		if(marc[prox]) continue;

		DFS(prox , i , sz);
	}
}

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);

		ingrau[n1]++;
		ingrau[n2]++;
	}

	lli line = 0;
	lli cycle = 0;

	for(int g = 1 ; g <= n ; g++)
	{
		if(ingrau[g] == 1 && !marc[g])
		{
			int size = 0;

			DFS(g , g , size);

			for(int k = 0 ; k < size ; k++)
			{
				lli sum = size - k - 1;
				sum *= size - k - 2;

				sum /= 2;

				line += 2*sum;
			}
		}
	}

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

		int size = 0;

		DFS(g , g , size);

		lli result = size;
		result *= size - 1;
		result *= size - 2;

		cycle += result;
	}

	printf("%lld\n",cycle + line);
}

Compilation message (stderr)

count_triplets.cpp: In function 'bool DFS(int, int, int&)':
count_triplets.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < grafo[i].size() ; g++)
                  ~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:37: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:41: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: 8 / 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