oj.uz

Submission #350947

# Submission time Handle Problem Language Result Execution time Memory
350947 2021-01-19T10:06:44 Z Saynaa Flood (IOI07_flood) C++14
100 / 100
 376 ms 29280 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 2;
const int D[4] = {1, 0, 3, 2};
bool mark[MAXN];
int n, w, s[MAXN];
vector< pair< int, int> > adj[MAXN][4];
vector< int > ans;
vector< pair<  pair< int, int> , int  > > vec;

void dfs(int v, int d){
	if( mark[v] ){
		s[v] = v;
		return;
	}
	mark[v] = true;
	for(int i = 0; i < 4; i ++){
		int dp = (D[i] + d) % 4;
		if(adj[v][dp].size()){
			int u = adj[v][dp].back().first, id = adj[v][dp].back().second;
			adj[v][dp].clear();
			adj[u][(dp + 2)%4].clear(); 
			dfs(u, dp);
			s[v] = s[u];
			if( s[u] == -1){
				ans.push_back(id);
				continue;
			}
			if(s[v] != v){
				mark[v] = false;
				return;
			}
				
		}
	}
	mark[v] = false;
	s[v] = -1;
	
	
	
	
	
}


int x[MAXN], y[MAXN];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> x[i] >> y[i];
		vec.push_back({{x[i], y[i]}, i});
	}
	sort(vec.begin(), vec.end());
	cin >> w;
	for(int i = 0; i < w; i ++){
		int a, b;
		cin >> a >> b, a --, b --;
		if( x[a] == x[b]){
			if( y[a] < y[b]){
				// a -> 0 , b -> 2
				adj[a][0].push_back({b, i}), adj[b][2].push_back({a, i});
			//	cout << '0' << endl;
			}
			else{
				// a -> 2, b -> 0
				adj[a][2].push_back({b, i}), adj[b][0].push_back({a, i});
			//	cout << '2' << endl;
			}
		}
		else{
			if( x[a] < x[b]){
				// a -> 1, b -> 3
				adj[a][1].push_back({b, i}), adj[b][3].push_back({a, i});
			//	cout << '1' << endl;
			}
			else{
				// a -> 3, b -> 1
				adj[a][3].push_back({b, i}), adj[b][1].push_back({a, i});
			//	cout << '3' << endl;
			}
			
		}
	}
	//sort(vec.begin(), vec.end());
	for(int i = 0; i < vec.size(); i ++){
		if( !mark[vec[i].second]) dfs(vec[i].second, 0);
	}
	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i ++)
		cout << ans[i] + 1 << endl;
	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i = 0; i < vec.size(); i ++){
      |                 ~~^~~~~~~~~~~~
flood.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0; i < ans.size(); i ++)
      |                 ~~^~~~~~~~~~~~

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 6 ms 9708 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 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 8 ms 9836 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 8 ms 9836 KB Output is correct
2 Correct 8 ms 9836 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11880 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 19312 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 17632 KB Output is correct
2 Correct 317 ms 22368 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20840 KB Output is correct
2 Correct 346 ms 22496 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 22240 KB Output is correct
2 Correct 376 ms 29280 KB Output is correct