Submission #254858

#	Time	Username	Problem	Language	Result	Execution time	Memory
254858		Lawliet	Bridges (APIO19_bridges)	C++17	13 / 100	3070 ms	4348 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

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

int n, m, q;

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

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

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

	scanf("%d",&q);

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

		if( type == 1 )
		{
			int ind, newW;
			scanf("%d %d",&ind,&newW);

			W[ind] = newW;
		}
		if( type == 2 )
		{
			int s, maxW;
			scanf("%d %d",&s,&maxW);

			initDSU();

			for(int j = 1 ; j <= m ; j++)
				if( W[j] >= maxW ) join( U[j] , V[j] );

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

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:40: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:43: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:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&ind,&newW);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:62:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&s,&maxW);
    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27