Submission #519751

#	Time	Username	Problem	Language	Result	Execution time	Memory
519751		sofapuden	Flood (IOI07_flood)	C++14	100 / 100	215 ms	24416 KiB

flood

#include<bits/stdc++.h>

using namespace std;

int n, m;

vector<array<int,3>> v, v2;
vector<vector<array<int,2>>> gr;
vector<int> us;
vector<int> vis;

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

bool go(int dir, int a, int b){
	auto x = v[a];
	auto y = v[b];
	int am = 0;
	am+=((y[0]-x[0] == dx[dir]) || (y[0]-x[0])*dx[dir] > 0);
	am+=((y[1]-x[1] == dy[dir]) || (y[1]-x[1])*dy[dir] > 0);
	return am == 2;
}

int dfs(int x, int dir, set<int> &path){
	if(path.count(x))return x;
	path.insert(x);
	for(int i = 0; i < 3; ++i){
		for(auto &y : gr[x]){
			if(go((dir+i)%4,x,y[0])){
				if(vis[y[1]])continue;
				vis[y[1]] = 1;
				int z = dfs(y[0],(dir+i+3)%4,path);
				if(z != -1){
					us[y[1]] = 1;
					if(z == x)break;
					path.erase(x);
					return z;
				}
			}
		}
	}
	path.erase(x);
	return -1;
}

bool cmp(array<int,3> &a, array<int,3> &b){
	if(a[0] == b[0] && a[1] == b[1])return a[2] < b[2];
	if(a[1] == b[1])return a[0] < b[0];
	return a[1] < b[1];

}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	v.resize(n);
	gr.resize(n);
	for(int i = 0; i < n; ++i){
		cin >> v[i][0] >> v[i][1];
		v[i][2] = i;
	}
	v2 = v;
	sort(v2.begin(),v2.end(),cmp);
	cin >> m;
	us.resize(m);
	vis.resize(m);
	for(int i = 0; i < m; ++i){
		int a, b; cin >> a >> b;
		a--, b--;
		gr[a].push_back({b,i});
		gr[b].push_back({a,i});
	}
	for(int i = 0; i < n; ++i){
		set<int> S;
		dfs(v2[i][2],0,S);
	}
	vector<int> rem;
	for(int i = 0; i < m; ++i){
		if(!us[i])rem.push_back(i+1);
	}
	cout << rem.size() << '\n';
	for(auto x : rem)cout << x << '\n';
}

• 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: 9 / 9