Submission #254861

#	Time	Username	Problem	Language	Result	Execution time	Memory
254861		Lawliet	Bridges (APIO19_bridges)	C++17	0 / 100	108 ms	4472 KiB

bridges

#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 (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27