oj.uz

Submission #158116

# Submission time Handle Problem Language Result Execution time Memory
158116 2019-10-14T20:48:23 Z faremy Flood (IOI07_flood) C++14
100 / 100
 103 ms 18036 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2232 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8672 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 6904 KB Output is correct
2 Correct 91 ms 9004 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8568 KB Output is correct
2 Correct 102 ms 8888 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8796 KB Output is correct
2 Correct 93 ms 18036 KB Output is correct