oj.uz

Submission #135122

# Submission time Handle Problem Language Result Execution time Memory
135122 2019-07-23T16:19:05 Z Lawliet Duathlon (APIO18_duathlon) C++14
5 / 100
 1000 ms 2040 KB 
#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;

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

	lli aux = grafo[i];

	while(aux != 0)
	{
		lli prox = aux&-aux;

		aux -= prox;

		float l = log2(prox);

		int p = l;

		if(bit(marc , p)) continue;

		DFS(p , 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] += (1LL << n2);
		grafo[n2] += (1LL << 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);
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:72: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:76: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 23 ms 376 KB Output is correct
10 Correct 525 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 252 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 23 ms 376 KB Output is correct
10 Correct 525 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 252 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 380 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 47 ms 376 KB Output is correct
39 Execution timed out 1069 ms 256 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 1016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 23 ms 376 KB Output is correct
10 Correct 525 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 252 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 380 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 47 ms 376 KB Output is correct
39 Execution timed out 1069 ms 256 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 23 ms 376 KB Output is correct
10 Correct 525 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 252 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 380 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 256 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 256 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 256 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 380 KB Output is correct
32 Correct 2 ms 256 KB Output is correct
33 Correct 2 ms 256 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 380 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 47 ms 376 KB Output is correct
39 Execution timed out 1069 ms 256 KB Time limit exceeded
40 Halted 0 ms 0 KB -