oj.uz

Submission #254861

# Submission time Handle Problem Language Result Execution time Memory
254861 2020-07-30T18:27:09 Z Lawliet Bridges (APIO19_bridges) C++17
0 / 100
 108 ms 4472 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 50010;
const int MAXM = 100010;

int n, m, q;

int ord[MAXM];
int U[MAXM], V[MAXM], W[MAXM];
int anc[MAXN], sz[MAXN], pW[MAXN];

int find(int cur, int w = 0)
{
	if( anc[cur] == cur || pW[cur] < w ) return cur;
	return find( anc[cur] , w );
}

void join(int i, int j, int w)
{
	i = find(i); j = find(j);

	if( i == j ) return;

	if( sz[i] < sz[j] )
		swap( i , j );

	pW[j] = w;
	anc[j] = i;
	sz[i] += sz[j];
}

bool cmp(int i, int j) { return W[i] > W[j]; }

void initDSU()
{
	for(int i = 1 ; i <= n ; i++)
		sz[i] = 1, anc[i] = i;
}

int main()
{
	scanf("%d %d",&n,&m);

	initDSU();

	for(int i = 1 ; i <= m ; i++)
		scanf("%d %d %d",&U[i],&V[i],&W[i]);

	iota( ord + 1 , ord + m + 1 , 1 );
	sort( ord + 1 , ord + m + 1 , cmp );

	for(int i = 1 ; i <= m ; i++)
		join( U[ ord[i] ] , V[ ord[i] ] , W[ ord[i] ] );

	scanf("%d",&q);

	for(int i = 1 ; i <= q ; i++)
	{
		int s, maxW;
		scanf("%*d %d %d",&s,&maxW);

		printf("%d\n",sz[ find(s , maxW) ]);
	}
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U[i],&V[i],&W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%*d %d %d",&s,&maxW);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 4472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 3192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -