Submission #254907

#	Time	Username	Problem	Language	Result	Execution time	Memory
254907		Lawliet	Bridges (APIO19_bridges)	C++17	59 / 100	3078 ms	10340 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int MAXN = 100010;
 
int n, m, q;
int raizQ;
 
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< 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];
}
 
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;
}
 
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 = sqrt(q) + 1;
 
	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;
	}
 
	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;
			}
		}
 
		sweep.clear();
 
		for(int i = 1 ; i <= m ; i++)
			if( !insideBlock[i] ) sweep.push_back( { lastWeight[i] , { U[i] , V[i] } } );//, printf("Adicionei %d: %d -> %d com peso %d\n",i,U[i],V[i],lastWeight[i]);
 
		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.push_back( { maxW , { -source , i } } );
			}
		}
 
		//printf("\n\n\n");
		//printf("------- Sweep Algorithm\n");
 
		sort( sweep.begin() , sweep.end() );
 
		initDSU();
 
		for(int i = (int)sweep.size() - 1 ; i >= 0 ; i--)
		{
			int type = 0;
			if( sweep[i].second.first < 0 ) type = 1;
 
			if( type == 0 )//Update
			{
				int curU = sweep[i].second.first;
				int curV = sweep[i].second.second;
 
				//printf("Juntei %d %d\n",curU,curV);
 
				join( curU , curV );
			}
			if( type == 1 )
			{
				int maxW = sweep[i].first;
				int ind = sweep[i].second.second;
				int source = -sweep[i].second.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();
					}
				}
			}	
		}
	}
 
	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:69: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:72: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:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:85: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:92: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: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27