제출 #135115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135115		Lawliet	철인 이종 경기 (APIO18_duathlon)	C++14	5 / 100	1079 ms	5880 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;

lli can;
lli marc;

vector<int> grafo[MAX];

stack<int> s;

bool bit(lli v, int i)
{
	if(v & (1LL << i)) return true;
	return false;
}

void DFS(int i, int t)
{
	if(i == t)
	{
		//printf("oi\n");
		while(!s.empty())
		{
			if(!bit(can , s.top()))
				can += (1LL << s.top());
			//printf("can = %d\n",can);
			s.pop();
		}

		return;
	}

	if(!bit(marc , i)) s.push( i );

	marc += (1LL << i);

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

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

		if(bit(marc , prox)) continue;

		DFS(prox , t);
	}

	if(bit(marc,i))
		marc -= (1LL << i);

	if(!s.empty() && s.top() == i)
		s.pop();
}

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 = s + 1 ; t <= n ; t++)
		{

			DFS(s , t);

			//printf("i =%d  %d\n",s,t);
			ans += __builtin_popcountll(can);

			if(bit(can,s)) ans--;
			if(bit(can,t)) ans--;

			//printf("\n\n");
			//printf("ans = %lld\n",ans);
			can = 0;
			//memset(can , false , sizeof(can));
		}

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

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

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

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void DFS(int, int)':
count_triplets.cpp:46: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:66: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:70: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