Submission #1146604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146604		Tsagana	Flood (IOI07_flood)	C++20	100 / 100	53 ms	18368 KiB

flood

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

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]].F;
		if (!k) continue ;
		
		adj[u][a[d][i]].F = 0;
		adj[k][(a[d][i] + 2) % 4].F = 0;
		
		int tmp = dfs(k, a[d][i]);
		
		if (tmp != -1) {if (tmp != u) {vis[u] = 0; return tmp;}}
		else {v.pb(adj[u][a[d][i]].S);}
	}
	vis[u] = 0;
	return -1;
}

void solve ()
{
	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].F.F - p[c].F.F;
		y = p[b].F.S - p[c].F.S;
		
		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(all(p));
	for (int i = 1; i <= n; i++) dfs(p[i].S, 0);
	cout << v.size() << '\n';

	for (int i: v) cout << i << '\n';
}
signed main() {IOS solve(); 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