oj.uz

Submission #366894

# Submission time Handle Problem Language Result Execution time Memory
366894 2021-02-15T16:23:29 Z CaroLinda Flood (IOI07_flood) C++14
91 / 100
 384 ms 43884 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 ;
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 8 ms 9836 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 8 ms 9708 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 8 ms 9836 KB Output is correct

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13164 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 25324 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 22680 KB Output is correct
2 Correct 281 ms 28456 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 26608 KB Output is correct
2 Correct 286 ms 28392 KB Output is correct

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 28264 KB Output is correct
2 Runtime error 384 ms 43884 KB Memory limit exceeded