Submission #254864

#	Time	Username	Problem	Language	Result	Execution time	Memory
254864		Lawliet	Bridges (APIO19_bridges)	C++17	0 / 100	111 ms	6244 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 50010;

int n, m, q;

int ans[MAXN];
int anc[MAXN], sz[MAXN];

vector< pair<int,pii> > sweep;

int find(int cur)
{
	if( anc[cur] == cur ) return cur;
	return anc[cur] = find( anc[cur] );
}
 
void join(int i, int j)
{
	i = find(i); j = find(j);
 
	if( i == j ) return;
 
	if( sz[i] < sz[j] )
		swap( i , j );
 
	anc[j] = i;
	sz[i] += sz[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++)
	{
		int U, V, W;
		scanf("%d %d %d",&U,&V,&W);

		sweep.push_back( { W , { U , V } } );
	}

	scanf("%d",&q);

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

		sweep.push_back( { maxW , { -s , i } } );
	}

	sort( sweep.begin() , sweep.end() );
	reverse( sweep.begin() , sweep.end() );

	for(int i = 0 ; i < (int)sweep.size() ; i++)
	{
		int U = sweep[i].second.first;
		int V = sweep[i].second.second;

		if( U > 0 ) join( U , V );
		else ans[V] = sz[ find(-U) ];
	}

	for(int i = 1 ; i <= q ; i++)
		printf("%d\n",ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:42: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,&V,&W);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:59: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