Submission #334934

#	Time	Username	Problem	Language	Result	Execution time	Memory
334934		CaroLinda	Flood (IOI07_flood)	C++14	64 / 100	1142 ms	64512 KiB

flood

#include <bits/stdc++.h>

#define debug printf
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )

const int MAX = 1e5+2 ;
const int MAXT = 4e5+10 ;

using namespace std ;

int N , W ;
vector<int> dsu(1), dist(1) ;
vector< vector<int> > adj(1) ;
pair<int,int> points[MAX] , Lines[MAX*2] ;
map< pair<int,int> , int > vertices ;
set< pair<int,int> > vis , sweep ;
vector< tuple<int,int,int> > freq[2] , walls[2] ;
map<int,int> compression ;

void add( pair<int,int> p )
{
	if( vertices.find(p) != vertices.end() ) return ;

	vertices.insert( make_pair(p, sz(vertices)+1 ) ) ;

	dsu.push_back( sz(vertices) ) ;
	dist.push_back(0) ;
	adj.push_back( vector<int>() );

	freq[0].push_back( make_tuple(p.second,p.first, sz(vertices) ) ) ;
	freq[1].push_back( make_tuple(p.first, p.second, sz(vertices) ) ) ;
}

int find(int x) 
{
	if(x == dsu[x] ) return x; 
	return dsu[x] = find(dsu[x] ) ;
}
void join(int x, int y )
{
	x = find(x);
	y = find(y) ;

	if( x == y) return ;

	if(rand() % 2 ) swap(x,y) ;

	dsu[x] = y ;
}

void bfs(int s )
{

	vector<int> fila(1,s) ;
	int ini = 0 ;
	dist[s] = 1 ;

	while( ini < sz(fila ) )
	{
		int x = fila[ini++] ;

		for(auto e : adj[x] )
		{
			if( dist[e] ) continue ;

			dist[e] = dist[x] + 1 ;
			fila.push_back(e) ;

		}

	}
	
}

int main()
{
	scanf("%d", &N) ;
	for(int i = 0 ; i < N ; i++ )
	{
		scanf("%d %d", &points[i].first, &points[i].second ) ;
		
		compression[ points[i].first ] = 0 ;
		compression[ points[i].second ] = 0 ;
	}

	scanf("%d", &W ) ;
	for(int i = 0, A, B ; i < W ; i++ )
	{
		scanf("%d %d", &Lines[i].first, &Lines[i].second ) ;
	
		Lines[i].first-- ;
		Lines[i].second-- ;

		A = Lines[i].first ;
		B = Lines[i].second ;
		
		compression[ points[A].first+1 ] = 0 ;
		compression[ points[A].second+1 ] = 0 ;
		compression[ points[B].first+1 ] = 0 ;
		compression[ points[B].second+1 ] = 0 ;
	}

	int Key = 1 ;
	for(auto &e : compression ) e.second = Key++ ;

	for(int i= 0 ; i < N ; i++ )
	{
		points[i].first = compression[ points[i].first ] ;
		points[i].second = compression[ points[i].second ] ;

		add( make_pair( points[i].first, points[i].second) )  ;
		add( make_pair( points[i].first+1, points[i].second) ) ;
		add( make_pair( points[i].first, points[i].second+1) ) ;
		add( make_pair( points[i].first+1, points[i].second+1) ) ;
	}

	compression.clear() ;

	for(int i = 0, A, B ; i < W ; i++ )
	{
		A = Lines[i].first ;
		B = Lines[i].second ;	

		if( points[A].first == points[B].first )
		{
			if( points[B].second < points[A].second ) swap(A,B) ;

			walls[0].push_back(make_tuple( points[A].second+1 , points[A].first+1, -i-1 ) ) ;
			walls[0].push_back(make_tuple( points[B].second+1, points[B].first+1 , i+1 ) ) ; 

			Lines[i] = make_pair( vertices[make_pair(points[A].first,points[A].second+1)] , vertices[ make_pair(points[A].first+1, points[A].second+1)] ) ;
		}
		else 
		{
			if( points[B].first < points[A].first ) swap(A,B) ;

			walls[1].push_back(make_tuple( points[A].first+1, points[A].second+1, -i-1 ) ) ;
			walls[1].push_back(make_tuple(points[B].first+1, points[B].second+1, i+1 ) ) ;

			Lines[i] = make_pair( vertices[make_pair(points[A].first+1, points[A].second) ], vertices[ make_pair(points[A].first+1, points[A].second+1) ] ) ;
		}

	}

	//0 means I'm joining elements in the same row
	//1 means I'm joining elements in the same column
	for(int ori = 0 ; ori < 2 ; ori++ )
	{
		sort(all(freq[ori] ) ) ;
		sort(all(walls[ori]) ) ;

		int ptrFreq = 0 , ptrWalls = 0 ;

		for(int i = 0 ; i < MAXT ; i++ )
		{
			while( ptrWalls < sz(walls[ori]) && get<0>(walls[ori][ptrWalls]) == i )
			{
				
				if( get<2>(walls[ori][ptrWalls]) < 0 ) sweep.insert( make_pair( get<1>(walls[ori][ptrWalls]) , get<2>(walls[ori][ptrWalls]) ) ) ;
				else sweep.erase( sweep.find(make_pair( get<1>(walls[ori][ptrWalls]) , -get<2>(walls[ori][ptrWalls]) ) ) ) ;

				ptrWalls++ ;
			}

			int aux = ptrFreq ;

			while( ptrFreq < sz(freq[ori] ) && get<0>(freq[ori][ptrFreq]) == i ) { ptrFreq++ ; }

			for(; aux < ptrFreq - 1 ; aux++ )
			{
				auto it = sweep.upper_bound( make_pair( get<1>(freq[ori][aux]) , 0 ) ) ;

				if(it != sweep.end() && it->first <= get<1>( freq[ori][aux+1] ) ) continue ;

				int u = get<2>( freq[ori][aux] ) ;
				int v = get<2>( freq[ori][aux+1] ) ;

				join(u,v) ;

			}
			
		}

		freq[ori].clear() ;  freq[ori].shrink_to_fit() ;
		walls[ori].clear() ; walls[ori].shrink_to_fit() ;

	}

	for(auto e : Lines ) 
	{
		adj[ find(e.first) ].push_back( find(e.second) ) ;
		adj[ find(e.second) ].push_back( find(e.first) ) ;
	}

	for(auto e : vertices) vis.insert( make_pair(e.first.first, e.first.second ) ) ;

	while( !vis.empty() )
	{
		int x = vertices[ make_pair( vis.begin()->first, vis.begin()->second) ] ;
		vis.erase( vis.begin() ) ;

		if( dist[find(x) ] ) continue ;

		bfs( find(x) ) ;
	}

	vector<int> ans ;

	for(int i = 0 ; i < W ; i++ )
		if( dist[ find(Lines[i].first) ] == dist[ find(Lines[i].second) ] ) ans.push_back(i+1) ;

	printf("%d\n", sz(ans ) ) ;
	for(auto e :ans ) printf("%d\n", e ) ;	

}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%d", &N) ;
      |  ~~~~~^~~~~~~~~~
flood.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d %d", &points[i].first, &points[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d", &W ) ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |   scanf("%d %d", &Lines[i].first, &Lines[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9