Submission #314670

#	Time	Username	Problem	Language	Result	Execution time	Memory
314670		CaroLinda	Bridges (APIO19_bridges)	C++14	73 / 100	3069 ms	22672 KiB

bridges

#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define sz(x) (int)(x.size())
#define perfectQ 600
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

const int MAX_COMPRESSION = 2e5+10 ;	
const int MAXQ = 1e5+10 ;
const int MAXM = 1e5+10 ;
const int MAXN = 5e4+10 ;

using namespace std ;

int N , M , Q ;
int indexEdge[MAXM] ;
int U[MAXM] , V[MAXM] , W[MAXM] ;
int ansQueries[MAXQ] ;
vector<int> adj[MAXN] ;
vector<int> freq[ MAX_COMPRESSION ] , smallSweep[ MAX_COMPRESSION ] ;
pair<int,int> queries[MAXQ] ;
bool jaPassei[MAXM] , vis[MAXN] ;

int pai[MAXN] ;
int componentSize[MAXN] ;

int find(int x)
{
	if(x == pai[x]) return x ;
	return pai[x] = find(pai[x]) ;
}

void join(int x, int y)
{
	x = find(x) ;
	y = find(y) ;

	if(x == y) return ;

	if( componentSize[x] > componentSize[y] )
		swap(x,y) ;

	componentSize[y] += componentSize[x] ;
	pai[x] = y ;

}

char c;
void read(int &num)
{
	num = 0 ;
	c = getchar() ;

	for(; (c > 47 &&  c < 58) ; c = getchar() )
		num = num*10 + (int)(c - '0') ; 
}

int main()
{

	read(N) ; read(M) ;

	vector<int> compression ;

	for(int i = 1 ; i <= M ; i++ )
	{
		read(U[i]) ;
		read(V[i]) ;
		read(W[i]) ;
		compression.push_back(W[i]) ;
	}

	read(Q) ;

	for(int i = 1 , t ; i <= Q ; i++ )
	{
		read(t); 
		read(queries[i].first); 
		read(queries[i].second) ;

		swap(queries[i].first, queries[i].second) ;

		if(t == 1)  
		{
			compression.push_back(queries[i].first) ;
			continue ;
		}
		 
		compression.push_back( queries[i].first ) ;
		queries[i].second *= -1 ;

	}

	sort(all(compression)) ;
	compression.erase( unique(all(compression)) , compression.end() ) ;

	for(int i = 1 ; i <= M ; i++ )
	{
		int l = 0 , r = sz(compression)-1 , mid ;
		while(l <= r)
		{
			mid = (l+r)>>1 ;
			if(compression[mid] < W[i]) l = mid+1 ;
			else if(compression[mid] > W[i]) r =mid-1 ;
			else 
			{
				W[i] = mid ;
				break ;
			}
		}
	}

	for(int i = 1 ; i <= Q ; i++ )
	{
		int &x = queries[i].first ;
		int y = queries[i].second ;

		int l = 0 , r = sz(compression)-1 , mid ;

		while(l <= r) 
		{
			mid = (l+r)>>1 ;

			if(compression[mid] < x ) l = mid+1 ;
			else if(compression[mid] > x ) r =mid-1 ;
			else 
			{
				x = mid ;
				break ;
			}

		}
	}

	 

	for(int i = 1 ; i <= M ; i++ )
	{
		indexEdge[i] = sz( freq[ W[i] ] ) ;
		freq[ W[i] ].push_back(i) ;
	}

	for(int i = 1 ; i <= Q ; i += perfectQ )
	{

		for(int j = 1 ; j <= N ; j++ ) 
		{
			pai[j] = j ;
			componentSize[j] = 1 ;
		}

		vector<int> updates ;

		for(int j = i ; j < min(i+perfectQ,Q+1) ; j++ )
		{
			if( queries[j].second > 0 )
			{
				updates.push_back(j) ;

				int m = queries[j].second ;
				
				if( indexEdge[m] == -1 ) continue ;

				swap( freq[ W[m] ][ indexEdge[m] ] , freq[ W[m] ][ sz(freq[W[m]])-1 ] ) ;
				freq[ W[m] ].pop_back() ;

				indexEdge[ freq[W[m]][indexEdge[m]] ] = indexEdge[m] ;
				indexEdge[m] = -1 ;

			}
			else smallSweep[ queries[j].first ].push_back(j) ;
		}

		 
		for(int j = sz(compression)-1 ; j >= 0 ; j-- )
		{
			for(int g : freq[j] ) join( U[g] , V[g] ) ;

			for(int g : smallSweep[j] ) 
			{
				vector<int> vec ;

				for(int k = sz(updates)-1 ; k >= 0 ; k-- )
				{
					int a = queries[ updates[k] ].first ;
					int b = queries[ updates[k] ].second ;

					if(updates[k] > g || jaPassei[b]) continue ;

					jaPassei[b] = true ;

					if( a < j ) continue ;

					adj[ find(U[b]) ].push_back( find(V[b]) ) ;
					adj[ find(V[b]) ].push_back( find(U[b]) ); 
				}

				for(int k = sz(updates)-1 ; k >= 0 ; k-- )
				{
					int a = queries[ updates[k] ].first ;
					int b = queries[ updates[k] ].second ;

					if(!jaPassei[b] && W[b] >= j ) 
					{
						adj[ find(U[b]) ].push_back( find(V[b]) ) ;
						adj[ find(V[b]) ].push_back( find(U[b]) ) ;
					}
				}

				
				int ini = 0 ;
				vector<int> fila(1,  find(-queries[g].second) ) ;
				vis[fila[0]] = true ;

				while(ini < sz(fila))
				{

					int x = fila[ini++ ];
					ansQueries[g] += componentSize[x] ;

					for(auto e : adj[x])
					{
						if(vis[e]) continue ;
						vis[e] = true ;
						fila.push_back(e) ;
					}

				}

				for(auto e : fila ) vis[e] = false ;

				for(int k : updates ) 
				{
					jaPassei[ queries[k].second ]  = false ;
					
					adj[ find(U[ queries[k].second ]) ].clear() ;
					adj[ find(V[ queries[k].second ]) ].clear() ;
				}

			}

			smallSweep[j].clear() ;

		}
		
		for(int k = sz(updates)-1 ; k >= 0 ; k-- )
		{
			int a = queries[ updates[k] ].first ;
			int b = queries[ updates[k] ].second ;

			if(indexEdge[b] != -1) continue ;

			W[b] = a ;
			indexEdge[b] = sz(freq[a]) ;
			freq[a].push_back(b) ;

		}
	}

	for(int i = 1 ; i <= Q ; i++ ) 
		if( queries[i].second < 0  ) printf("%d\n" , ansQueries[i]) ;

}

Compilation message (stderr)

bridges.cpp:10: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("O3")
      | 
bridges.cpp:11: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:121:7: warning: unused variable 'y' [-Wunused-variable]
  121 |   int y = queries[i].second ;
      |       ^
bridges.cpp:205:10: warning: unused variable 'a' [-Wunused-variable]
  205 |      int a = queries[ updates[k] ].first ;
      |          ^

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