oj.uz

Submission #334585

# Submission time Handle Problem Language Result Execution time Memory
334585 2020-12-09T13:57:10 Z CaroLinda Flood (IOI07_flood) C++14
64 / 100
 2000 ms 64368 KB 
#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 ;

using namespace std ;

struct Event
{

	int firstParameter , secondParameter , type ;	

	Event(int a=0, int b=0, int c=0) : firstParameter(a), secondParameter(b), type(c) {}
	bool operator < (Event other ) const 
	{
		if( firstParameter == other.firstParameter ) return type < other.type ;
		return firstParameter<other.firstParameter ;
	}

} ;

int N , W ;
int dsu[MAX*4] , dist[MAX*4] ;
vector< Event > joinRow, joinCol ;
vector<int> adj[ MAX*4 ] ;
pair<int,int> points[MAX] , Lines[MAX*2] ;
map< pair<int,int> , int > vertices ;
set< pair<int,int> > vis , sweep ;

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

	vertices.insert( make_pair(p, sz(vertices)+1 ) ) ;
	dsu[ sz(vertices) ] = sz(vertices) ;
	joinRow.push_back( Event(p.second,p.first, 1 ) ) ;
	joinCol.push_back( Event(p.first, p.second,1 ) ) ;
}

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

	scanf("%d", &W ) ;
	for(int i = 0, A, B ; i < W ; i++ )
	{
		scanf("%d %d", &A, &B ) ;
		--A, --B ;

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

			joinRow.push_back( Event(points[A].second+1,points[A].first+1,0) ) ;
			joinRow.push_back( Event(points[B].second+1, points[B].first+1 , -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) ;

			joinCol.push_back( Event(points[A].first+1, points[A].second+1, 0) ) ;
			joinCol.push_back( Event(points[B].first+1, points[B].second+1, -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) ] ) ;
		}

	}

	sort(all(joinRow) ) ;
	sort(all(joinCol) ) ;

	for(int i= 0 ; i < sz(joinRow) ; )
	{
		int j = i ;
		int firstParameter = joinRow[i].firstParameter ;

		while( j < sz(joinRow) && joinRow[j].firstParameter == firstParameter )
		{
			if( joinRow[j].type != -1 )
				sweep.insert( make_pair( joinRow[j].secondParameter,joinRow[j].type ) ) ; 

			else sweep.erase( sweep.find( make_pair( joinRow[j].secondParameter, 0 ) ) ) ;
			j++ ;
		}

		auto it = sweep.begin() ;
		auto nxt = it ; nxt++ ;

		while(nxt != sweep.end() ) 
		{
			if( it->second == 1 && nxt->second == 1 ) 
				join( vertices[make_pair(it->first, firstParameter) ], vertices[ make_pair(nxt->first, firstParameter) ] ) ;
			it++ ;
			nxt++ ;
		}

		for(int g = i ; g < j ; g++ )
		{
			if( joinRow[g].type != 1 ) continue ; 
			sweep.erase( sweep.find( make_pair(joinRow[g].secondParameter,1) ) ) ;
		}

		i = j ;

	}

	joinRow.clear() ; joinRow.shrink_to_fit() ;

	for(int i = 0 ; i < sz(joinCol) ; )
	{
		int j = i ;
		int firstParameter = joinCol[i].firstParameter ;

		while( j < sz(joinCol) && joinCol[j].firstParameter == firstParameter )
		{

			if( joinCol[j].type != -1 )
				sweep.insert( make_pair( joinCol[j].secondParameter, joinCol[j].type ) ) ;
			else sweep.erase( sweep.find( make_pair( joinCol[j].secondParameter, 0 ) ) ) ;
			
			j++ ;
		}

		auto it = sweep.begin() ;
		auto nxt = it ; nxt++ ;

		while( nxt != sweep.end() )
		{
			if(it->second == 1 && nxt->second == 1 ) 
				join(vertices[make_pair(firstParameter, it->first)], vertices[make_pair(firstParameter, nxt->first) ] ) ;
			it++ ;
			nxt++ ;
		}
		
		for(int g = i ;  g < j ; g++ )
		{
			if( joinCol[g].type != 1 ) continue ;
			sweep.erase(sweep.find(make_pair(joinCol[g].secondParameter, 1) ) ) ;
		}

		i = j ;

	}

	joinCol.clear() ; joinCol.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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11872 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11872 KB Output is correct
2 Correct 12 ms 11872 KB Output is correct
3 Correct 14 ms 11872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12000 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12000 KB Output is correct
2 Correct 16 ms 12128 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12000 KB Output is correct
2 Correct 13 ms 12000 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12000 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12164 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12008 KB Output is correct
2 Correct 16 ms 12128 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12000 KB Output is correct
2 Correct 21 ms 12000 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 23752 KB Output is correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 38472 KB Time limit exceeded

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 48820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1283 ms 62824 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1351 ms 64368 KB Memory limit exceeded
2 Halted 0 ms 0 KB -