oj.uz

Submission #159879

# Submission time Handle Problem Language Result Execution time Memory
159879 2019-10-25T07:08:53 Z chitz Flood (IOI07_flood) C++14
100 / 100
 183 ms 18020 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 3 ms 504 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 376 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 6 ms 376 KB Output is correct

Subtask #4
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 #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2244 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8692 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6880 KB Output is correct
2 Correct 183 ms 9168 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8668 KB Output is correct
2 Correct 136 ms 9000 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 8848 KB Output is correct
2 Correct 130 ms 18020 KB Output is correct