Submission #135058

#	Time	Username	Problem	Language	Result	Execution time	Memory
135058		Lawliet	Duathlon (APIO18_duathlon)	C++14	5 / 100	1086 ms	11124 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;

bool can[MAX];
bool marc[MAX];

vector<int> s;

vector<int> grafo[MAX];

void DFS(int i, int t)
{
	if(i == t)
	{
		for(int g = 1 ; g < s.size(); g++)
			can[ s[g] ] = true;

		return;
	}

	marc[i] = true;
	s.push_back( i );

	//printf("i = %d\n",i);

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

		if(marc[prox]) continue;

		//printf("i = %d prox = %d\n",i,prox);

		DFS(prox , t);
	}

	marc[i] = false;
	s.pop_back();
}

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 s = 1 ; s <= n ; s++)
	{
		for(int t = 1 ; t <= n ; t++)
		{
			if(s == t) continue;

			DFS(s , t);

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

			memset(can , false , sizeof(can));
		}

		//printf("---- %lld\n",ans);

		//printf("\n\n");
	}

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

Compilation message (stderr)

count_triplets.cpp: In function 'void DFS(int, int)':
count_triplets.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int g = 1 ; g < s.size(); g++)
                   ~~^~~~~~~~~~
count_triplets.cpp:35: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:52: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:56: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: 5 / 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