Submission #366894

#	Time	Username	Problem	Language	Result	Execution time	Memory
366894		CaroLinda	Flood (IOI07_flood)	C++14	91 / 100	384 ms	43884 KiB

flood

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)(x.size() )

const int MAXN = 1e5+5 ;

using namespace std ;

int N , M ;
multiset< int > walls ;
vector< pair<int,int> > adj[MAXN][4] ;
pair<int,int> p[MAXN] ;
vector<int> ans ;

struct cmp{
	bool operator () ( const int &a, const int &b ) const { return p[a] < p[b] ; }
} ;
set<int, cmp> points ;

void dfs(int x, int dir, int t )
{	
	int save_dir = dir-1 ;
	dir-- ;

	pair<int,int> k = make_pair(-1,-1) ;

	do		
	{
		if( dir < 0 ) dir += 4 ;
		if( dir == 4 ) dir = 0 ;	

		if( sz(adj[x][dir]) == 0 || (adj[x][dir][0].second < 0 && adj[x][dir][0].second > t ) ) 
		{
			dir++ ;
			continue ;
		}

		if( adj[x][dir][0].second < 0 && adj[x][dir][0].second == t ) return ;

		walls.insert(adj[x][dir][0].second) ;

		int y = adj[x][dir][0].first ;

		adj[x][dir][0].second = t ;

		k = make_pair(y, (dir+2)%4 ) ;

		dfs(y, dir, t) ;

		break ;

	} while( dir != save_dir ) ;

	if( k.first == -1 ) return ;

	adj[k.first][k.second].erase( all(adj[k.first][k.second] ) ) ;
	adj[x][ (k.second+2)%4 ].erase( all(adj[x][ (k.second+2) % 4 ] ) ) ;

}

int main()
{
	scanf("%d", &N ) ;
	for(int i= 1 ; i <= N ; i++ )
	{
		scanf("%d %d", &p[i].first, &p[i].second ) ;
		points.insert(i) ;
	}
	scanf("%d", &M ) ;
	for(int i = 1 , a , b  ; i<= M ; i++ )
	{
		scanf("%d %d", &a, &b ) ;

		if( p[a] > p[b] ) swap(a,b) ;

		if( p[a].first == p[b].first )
		{
			adj[a][0].push_back( make_pair(b, i) ) ;
			adj[b][2].push_back( make_pair(a,i) ) ;
		}
		else
		{
  			adj[a][1].push_back( make_pair(b, i) ) ;
  			adj[b][3].push_back( make_pair(a,i) ) ;
		}
	}

	int tempo = 0 ;

	while( !points.empty() )
	{
		int x = *points.begin() ;
		points.erase( points.begin() ) ;

		walls.clear() ;
		tempo-- ;

		for(int i = 0 ; i <= 1 ; i++ )
		{
			if( sz(adj[x][i]) == 0 || (adj[x][i][0].second < 0 && adj[x][i][0].second > tempo) ) continue ;

			walls.insert(adj[x][i][0].second) ;

			int y = adj[x][i][0].first ;

			adj[x][i][0].second = tempo ;

			dfs(y, i, tempo) ;

			break ;
		}

		while( !walls.empty() )
		{
			int x = *walls.begin() ;
			walls.erase( walls.begin() ) ;

			if( walls.find(x) != walls.end() ) ans.push_back(x) ;

		}

	}

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

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d %d", &p[i].first, &p[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |  scanf("%d", &M ) ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   scanf("%d %d", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• 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: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 0 / 9