Submission #350940

#	Time	Username	Problem	Language	Result	Execution time	Memory
350940		Saynaa	Flood (IOI07_flood)	C++14	91 / 100	434 ms	38828 KiB

flood

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
const int D[4] = {1, 0, 3, 2};
bool mark[MAXN];
int n, w, s[MAXN];
vector< pair< int, int> > adj[MAXN][7];
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;
			}
			
		}
	}
	
	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 (stderr)

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 / 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