Submission #1146590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146590		Tsagana	Flood (IOI07_flood)	C++20	55 / 100	49 ms	9032 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;

int n, m;
pair<int, int> adj[200010][4];
pair<int, int> a[200010];
vector<int> ans;
int vis[200010];
int s[20010];

bool cmp(int x, int y) {return a[x] < a[y];}

int calc(int x, int d)
{
	if (vis[x]) return x;
	vis[x] = 1;
	for (int i = 0; i < 4; i++)
	{
		int tod = (d - i + 1 + 4) % 4;
		int to = adj[x][tod].F;
		if (to == -1) continue;
		
		int ed = adj[x][tod].S;
		adj[x][tod] = {-1, -1};
		adj[to][(tod+2)%4] = {-1, -1};

		int y = calc(to, tod);
		
		if (y == -1) {ans.pb(ed); continue;}
		if (y != x) {vis[x] = 0; return y;}
	}
	vis[x] = 0;
	return -1;
}

void solve ()
{
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		s[i] = i;
		cin >> a[i].F >> a[i].S;
		for (int j = 0; j < 4; j++) adj[i][j] = {-1, -1};
	}
	sort(s, s + n, cmp);
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y; cin >> x >> y; x--; y--;
		if (a[x].F == a[y].F)
		{
			if (a[x].S > a[y].S) swap(x, y);
			adj[x][0] = {y, i};
			adj[y][2] = {x, i};
		}
		else
		{
			if (a[x].F > a[y].F) swap(x, y);
			adj[x][1] = {y, i};
			adj[y][3] = {x, i};
		}
	}
	for (int i = 0; i < n; i++) calc(s[i], 0);
	
	cout << ans.size() << '\n';
	for (int i: ans) 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: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9