Submission #1182524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182524		dugersuren	Flood (IOI07_flood)	C++20	100 / 100	88 ms	18364 KiB

flood

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<pair<int, int> , int> > p;
pair<int, int> adj[100010][4];
bool vis[100010];
vector<int> v;
int xac = 0;
int a[4][4];
int n, w;

int dfs(int u, int d){
	if (vis[u]) return u;
	vis[u]=1;
	for (int i=0;i<4;i++){
		int k=adj[u][a[d][i]].first;
		if (!k) continue ;
		
		adj[u][a[d][i]].first = 0;
		adj[k][(a[d][i] + 2) % 4].first= 0;
		
		int tmp = dfs(k, a[d][i]);
		
		if (tmp != -1) {if (tmp != u) {vis[u] = 0; return tmp;}}
		else {v.push_back(adj[u][a[d][i]].second);}
	}
	vis[u] = 0;
	return -1;
}


signed main() {
	ios_base::sync_with_stdio(false);cin.tie();cout.tie();
	cin >> n;
	for (int i = 0; i < 4; i++)
	{
		a[i][1] = i;
		a[i][0] = (i + 1) % 4;
		a[i][2] = (i + 3) % 4;
		a[i][3] = (i + 2) % 4;
	}
	p.resize(n + 1);
	p[0] = {{-1, -1}, -1};
	for (int i = 1; i <= n; i++)
	{
		int x, y; cin >> x >> y;
		p[i] = {{x, y}, i};
	}
	cin >> w;
	for (int i = 1; i <= w; i++)
	{
		int c, b; cin >> c >> b;
		int d, x, y;
		x = p[b].first.first - p[c].first.first;
		y = p[b].first.second - p[c].first.second;
		
		if (x) d = (x > 0 ? 1 : 3);
		else d = (y > 0 ? 0 : 2);

		adj[c][d] = {b, i};
		adj[b][(d+2)%4] = {c, i};
	}
	sort(p.begin(),p.end());
	for (int i = 1; i <= n; i++) dfs(p[i].second, 0);
	cout << v.size() << '\n';

	for (int i: v) cout << i << '\n';
	return 0;
}

• 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