Submission #135101

#	Time	Username	Problem	Language	Result	Execution time	Memory
135101		Lawliet	Duathlon (APIO18_duathlon)	C++14	5 / 100	1081 ms	12472 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)
	{
		while(!s.empty())
		{
			can[s.back()] = true;
			s.pop_back();
		}

		return;
	}

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

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

		if(marc[prox]) continue;

		DFS(prox , t);
	}

	marc[i] = false;

	if(!s.empty()&&s.back() == i)
		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);

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

			for(int g = 1 ; g <= n ; g++)
			{
				if(can[g] && g != s && g != t) ans++;
				can[g] = false;
			}

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

			//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:36: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:53: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:57: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