Submission #158116

#	Time	Username	Problem	Language	Result	Execution time	Memory
158116		faremy	Flood (IOI07_flood)	C++14	100 / 100	103 ms	18036 KiB

flood

#include <iostream>
#include <algorithm>
#include <vector>


const int MAXN = 1e5;

int x[MAXN], y[MAXN];
int order[MAXN];

int graph[MAXN][4];
int id[MAXN][4];
int degree[MAXN];

std::vector<int> standing;


void brk(int node, int dir, int start)
{
	for (int iDir = 5; iDir > 1; iDir--)
	{
		int nxt = graph[node][(dir + iDir) % 4];
		if (nxt != -1)
		{
			if (nxt != start)
				brk(nxt, (dir + iDir) % 4, start);

			if (graph[node][(dir + iDir) % 4] == -1)
				standing.emplace_back(id[node][(dir + iDir) % 4]);
			else
			{
				degree[node]--;
				degree[nxt]--;
				graph[node][(dir + iDir) % 4] = -1;
				graph[nxt][(dir + iDir + 2) % 4] = -1; 
			}
			
			return;
		}
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int points; std::cin >> points;
	for (int iPoint = 0; iPoint < points; iPoint++)
	{
		std::cin >> x[iPoint] >> y[iPoint];
		order[iPoint] = iPoint;

		for (int iDir = 0; iDir < 4; iDir++)
			graph[iPoint][iDir] = -1;
	}

	int walls; std::cin >> walls;
	for (int iWall = 0; iWall < walls; iWall++)
	{
		int u, v;
		std::cin >> u >> v;
		u--; v--;

		if (x[u] == x[v])
		{
			int dir = 0;
			if (y[u] > y[v])
				dir += 2;
			
			graph[u][dir] = v;
			graph[v][2 - dir] = u;
			id[u][dir] = iWall;
			id[v][2 - dir] = iWall;
		}
		else
		{
			int dir = 1;
			if (x[u] < x[v])
				dir += 2;
			
			graph[u][dir] = v;
			graph[v][4 - dir] = u;
			id[u][dir] = iWall;
			id[v][4 - dir] = iWall;
		}

		degree[u]++;
		degree[v]++;
	}

	std::sort(order, order + points, [](int a, int b) { return (x[a] < x[b]); });
	for (int iNode = 0; iNode < points; iNode++)
		while (degree[order[iNode]] != 0)
			brk(order[iNode], 0, order[iNode]);

	std::cout << standing.size() << '\n';
	for (int wall : standing)
		std::cout << wall + 1 << '\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