Submission #254904

#	Time	Username	Problem	Language	Result	Execution time	Memory
254904		Lawliet	Bridges (APIO19_bridges)	C++17	27 / 100	3076 ms	31316 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int MAXN = 100010;
const int MAXT = 200010;
 
int n, m, q;
int raizQ;
int cntWeight;
 
int ans[MAXN];
int indInside[MAXN];
int lastWeight[MAXN];
int anc[MAXN], sz[MAXN];
int U[MAXN], V[MAXN], W[MAXN];

bool mark[MAXN];
bool insideBlock[MAXN];
 
vector<int> adj[MAXN];

vector<pii> queries;
vector<pii> sweep[MAXT];
 
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];
}

bool isUpdate(int i)
{
	int val = queries[i].second;
	return ( val > 0 );
}

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

int DFS(int cur)
{
	mark[cur] = true;
	int ans = sz[cur];

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		if( !mark[ adj[cur][i] ] ) ans += DFS( adj[cur][i] );

	return ans;
}

void compress()
{
	set<int> s;
	map<int,int> conv;

	for(int i = 1 ; i <= m ; i++)
		s.insert( W[i] );

	for(int i = 0 ; i < q ; i++)
		s.insert( queries[i].first );

	for(auto it = s.begin() ; it != s.end() ; it++)
		conv[*it] = ++cntWeight;

	for(int i = 1 ; i <= m ; i++)
		W[i] = conv[ W[i] ];

	for(int i = 0 ; i < q ; i++)
		queries[i].first = conv[ queries[i].first ];
}
 
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);
	raizQ = 1200;
 
	for(int i = 1 ; i <= q ; i++)
	{
		int type;
		scanf("%d",&type);

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

			queries.push_back( { newW , edge } );
		}
		if( type == 2 )
		{
			int s, maxW;
			scanf("%d %d",&s,&maxW);

			queries.push_back( { maxW , -s } );
		}

		ans[i - 1] = -1;
	}

	compress();

	int lastBlock = (q - 1)/raizQ;

	for(int block = 0 ; block <= lastBlock ; block++)
	{
		//printf("+============================+ Processando bloco %d\n",block);

		int L = block*raizQ;
		int R = (block + 1)*raizQ - 1;
		R = min( R , q - 1 );

		for(int i = 1 ; i <= m ; i++)
		{
			lastWeight[i] = W[i];
			insideBlock[i] = false;
		}

		vector<int> inside;

		for(int i = L ; i <= R ; i++)
		{
			if( isUpdate( i ) ) 
			{
				int edge = queries[i].second;

				if( !insideBlock[edge] )
				{
					indInside[edge] = (int)inside.size();

					//printf(".. edge = %d\n",edge);
					insideBlock[edge] = true;
					inside.push_back( edge );
				}
			}
		}

		for(int i = 0 ; i < L ; i++)
		{
			if( isUpdate( i ) )
			{
				int newW = queries[i].first;
				int edge = queries[i].second;

				lastWeight[edge] = newW;
			}
		}

		for(int i = L ; i <= R ; i++)
		{
			if( !isUpdate( i ) )
			{
				int maxW = queries[i].first;
				int source = -queries[i].second;

				//printf("Achei query %d %d\n",source,maxW);

				sweep[maxW].push_back( { -source , i } );
			}
		}

		for(int i = 1 ; i <= m ; i++)
			if( !insideBlock[i] ) sweep[ lastWeight[i] ].push_back( { U[i] , V[i] } );//, printf("Adicionei %d: %d -> %d com peso %d\n",i,U[i],V[i],lastWeight[i]);

		//printf("\n\n\n");
		//printf("------- Sweep Algorithm\n");

		initDSU();

		for(int k = cntWeight ; k > 0 ; k--)
		{
			while( !sweep[k].empty() )
			{
				int type = 0;
				if( sweep[k].back().first < 0 ) type = 1;

				if( type == 0 )//Update
				{
					int curU = sweep[k].back().first;
					int curV = sweep[k].back().second;

					//printf("Juntei %d %d\n",curU,curV);

					join( curU , curV );
				}
				if( type == 1 )
				{
					int maxW = k;
					int ind = sweep[k].back().second;
					int source = -sweep[k].back().first;

					//printf("Respondendo query maxW = %d source = %d ind = %d\n",maxW,source,ind);

					vector<int> weightInside;

					for(int j = 0 ; j < (int)inside.size() ; j++)
						weightInside.push_back( lastWeight[ inside[j] ] );

					for(int j = L ; j <= ind ; j++)
					{
						if( isUpdate( j ) )
						{
							int newW = queries[j].first;
							int edge = queries[j].second;
					
							weightInside[ indInside[edge] ] = newW;
						}
					}

					for(int j = 0 ; j < (int)inside.size() ; j++)
					{
						//printf("...... Tentando colocar %d -> %d com peso %d\n",U[ inside[j] ],V[ inside[j] ],weightInside[j]);
						if( weightInside[j] >= maxW ) 
						{
							int curU = find( U[ inside[j] ] );
							int curV = find( V[ inside[j] ] );

							adj[curU].push_back( curV );
							adj[curV].push_back( curU );
						}
					}

					ans[ind] = DFS( find(source) );
					mark[ find(source) ] = false;

					for(int j = 0 ; j < (int)inside.size() ; j++)
					{
						if( weightInside[j] >= maxW ) 
						{
							int curU = find( U[ inside[j] ] );
							int curV = find( V[ inside[j] ] );

							mark[curU] = mark[curV] = false;

							adj[curU].clear();
							adj[curV].clear();
						}
					}
				}	

				sweep[k].pop_back();
			}
		}
	}
 
	for(int i = 0 ; i < q ; i++)
		if( ans[i] != -1 ) printf("%d\n",ans[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:92: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:95: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:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&edge,&newW);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:115: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: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27