oj.uz

답안 #334628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
334628 2020-12-09T15:21:38 Z CaroLinda Flood (IOI07_flood) C++14
64 / 100
 905 ms 65540 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 ;
const int MAXT = 4e5+10 ;

using namespace std ;

struct Bit
{

	int bit[MAXT] ;

	void upd(int i, int val) { for(; i < MAXT ; i += i &-i ) bit[i] += val ; }
	int qry(int i) 
	{
		int tot = 0 ;
		for(; i > 0 ; i -= i &-i ) tot += bit[i] ;
		return tot ;
	}

} bit ;

int N , W ;
int dsu[MAX*4] , dist[MAX*4] ;
vector<int> adj[ MAX*4 ] ;
pair<int,int> points[MAX] , Lines[MAX*2] ;
map< pair<int,int> , int > vertices ;
set< pair<int,int> > vis ;
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[ sz(vertices) ] = sz(vertices) ;

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

	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,1) ) ;
			walls[0].push_back(make_tuple( 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) ;

			walls[1].push_back(make_tuple( points[A].first+1, points[A].second+1, 1 ) ) ;
			walls[1].push_back(make_tuple(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) ] ) ;
		}

	}

	//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 )
			{
				bit.upd( 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++ )
			{
				if( bit.qry(get<1>(freq[ori][aux+1]) ) - bit.qry( get<1>(freq[ori][aux]) ) ) continue ;

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

				join(u,v) ;

			}
			
		}

	}

	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:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |  scanf("%d", &N) ;
      |  ~~~~~^~~~~~~~~~
flood.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   scanf("%d %d", &points[i].first, &points[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |  scanf("%d", &W ) ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%d %d", &Lines[i].first, &Lines[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12128 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12000 KB Output is correct
2 Correct 14 ms 12000 KB Output is correct
3 Correct 15 ms 12000 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12000 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12008 KB Output is correct
2 Correct 16 ms 12136 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12000 KB Output is correct
2 Correct 14 ms 12000 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 12000 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12128 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 12128 KB Output is correct
2 Correct 17 ms 12264 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 12136 KB Output is correct
2 Correct 17 ms 12128 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 27600 KB Output is correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 454 ms 51656 KB Memory limit exceeded

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 508 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 867 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 905 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -