oj.uz

Submission #366906

# Submission time Handle Problem Language Result Execution time Memory
366906 2021-02-15T17:05:29 Z CaroLinda Flood (IOI07_flood) C++14
100 / 100
 173 ms 19452 KB 
#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 , ans ;
vector< tuple<short int,int, int> > adj[MAXN] ;
pair<int,int> p[MAXN] ;
short int idx[4] ;
pair<short int,int> a ;
int p_idx[MAXN] ;
bool wall[2*MAXN] ;

void dfs(int x, short int dir, int yy, short int ddir )
{

	for(int i= 0 ; i < 4 ; i++ ) idx[i] = -1 ;
	
	for(int i = 0 ; i < sz(adj[x] ) ; i++ )
		idx[ get<0>(adj[x][i] ) ] = i ;	

	a = make_pair(0,0) ;

	for(int i = dir-1 , c = 0 ; c < 4 ; c++ , i++ )
	{
		if( i < 0 ) i += 4 ;
		if( i >= 4 ) i = 0 ;

		if( x == yy && i == ddir && idx[i] == -1 ) return ;
		if( idx[i] == -1 ) continue ;

		int y = get<1>(adj[x][idx[i] ]) ;

		adj[x].erase( adj[x].begin()+idx[i] , adj[x].begin()+idx[i]+1 ) ;

		dfs(y, i, yy, ddir ) ;

		a = make_pair( (i+2)%4, y ) ;

		break ;

	}

	if(!a.second) return;

	for(int i = 0 ; i < sz(adj[ a.second ] ) ; i++ )
	{
		if( get<0>(adj[a.second][i] ) != a.first ) continue ;
		
		wall[ get<2>(adj[a.second][i]) ] = true ;
		ans-- ;
		adj[a.second].erase( adj[a.second].begin() + i , adj[a.second].begin()+i+1 ) ;

		return ;
	}

}

int main()
{
	scanf("%d", &N ) ;
	for(int i= 1 ; i <= N ; i++ ) scanf("%d %d", &p[i].first, &p[i].second ) ;
	
	scanf("%d", &M ) ; ans = 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].push_back( make_tuple(0,b, i) ) ;
			adj[b].push_back( make_tuple(2,a,i) ) ;
		}
		else
		{
  			adj[a].push_back( make_tuple(1,b, i) ) ;
  			adj[b].push_back( make_tuple(3,a,i) ) ;
		}

	}

	for(int i = 1 ; i <= N ; i++ ) p_idx[i] = i ;
	sort(p_idx+1, p_idx+1+N, [&](int a, int b ) { return p[a] < p[b] ; } ) ;

	for(int j= 1 ; j <= N ; j++ )
	{
		int x = p_idx[j] ;

		sort(all(adj[x] ) ) ;

		for(int i = 0 ; i < sz(adj[x] ) ; i++ )
		{
			if( get<0>( adj[x][i] ) > 1 ) continue ;

			dfs(x, get<0>(adj[x][i])+1, x, get<0>(adj[x][i]) ) ;
			
			break ;

		}

	}

	printf("%d\n", ans ) ;

	for(int i = 1 ; i <= M ; i++ )
		if( !wall[i] ) printf("%d\n", i ) ;

}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:68:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  for(int i= 1 ; i <= N ; i++ ) scanf("%d %d", &p[i].first, &p[i].second ) ;
      |                                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |  scanf("%d", &M ) ; ans = M ;
      |  ~~~~~^~~~~~~~~~~
flood.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   scanf("%d %d", &a, &b ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4332 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 10476 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8940 KB Output is correct
2 Correct 163 ms 13384 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 12268 KB Output is correct
2 Correct 162 ms 14060 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 13164 KB Output is correct
2 Correct 139 ms 19452 KB Output is correct