oj.uz

Submission #109113

# Submission time Handle Problem Language Result Execution time Memory
109113 2019-05-04T11:29:47 Z MetB Flood (IOI07_flood) C++14
100 / 100
 646 ms 28864 KB 
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string>
#include <set>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <ctime>
#include <map>
#include <queue>
#include <bitset>

using namespace std;

const long long INF = 1e9 + 1, MOD = 998244353;

typedef long long ll;

struct point
{
	int x, y, ind;
	int l[4], e[4];

	bool operator < (const point& b) const
	{
		return (x == b.x ? y < b.y : x < b.x);
	}
} a[200000];

struct edge
{
	int x, y, ind;

	bool operator < (const edge& b) const
	{
		return ind < b.ind;
	}

} b[400000];

int degree[200000], n, w;

set <edge> to_erase, ans;
set <point> s;

void ccw (int x)
{
	int f = x;
	int pos = 2;

	do
	{
		int new_pos = (pos + 1) % 4;

		while (a[f].l[new_pos] == -1 || !degree[a[f].l[new_pos]])
		{
			new_pos--;
			if (new_pos < 0) new_pos = 3;
		}

		pos = new_pos;

		edge k = b[a[f].e[pos]];

		if (to_erase.find (k) == to_erase.end ()) to_erase.insert (k);
		else ans.insert (k);

		f = a[f].l[pos];
	}
	while (f != x);
}

int main ()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int x, y;
		scanf ("%d%d", &x, &y);
		a[i] = {x, y, i, -1, -1, -1, -1, -1, -1, -1, -1};
	}

	cin >> w;

	for (int i = 0; i < w; i++)
	{
		int x, y;

		scanf ("%d%d", &x, &y);
		x--;
		y--;

		b[i] = {x, y, i};

		if (x > y) swap (x, y);

		degree[x]++;
		degree[y]++;

		if (a[x].x == a[y].x)
		{
			if (a[x].y > a[y].y)
			{
				a[x].l[2] = y;
				a[x].e[2] = i;
				a[y].l[0] = x;
				a[y].e[0] = i;
			}
			else
			{
				a[x].l[0] = y;
				a[x].e[0] = i;
				a[y].l[2] = x;
				a[y].e[2] = i;
			}
		}
		else
		{
			if (a[x].x > a[y].x)
			{
				a[x].l[1] = y;
				a[x].e[1] = i;
				a[y].l[3] = x;
				a[y].e[3] = i;
			}
			else
			{
				a[x].l[3] = y;
				a[x].e[3] = i;
				a[y].l[1] = x;
				a[y].e[1] = i;
			}
		}
	}

	for (int i = 0; i < n; i++)
		if (degree[i]) s.insert (a[i]);

	while (!s.empty ())
	{
		point corner = *s.rbegin ();
		//cout << endl;

		to_erase.clear ();

		ccw (corner.ind);

		for (auto e : to_erase)
		{
			//cout << a[e.x].x << ' ' << a[e.x].y << ' ' << a[e.y].x << ' ' << a[e.y].y << endl;
			degree[e.x]--;
			degree[e.y]--;

			if (a[e.x].x == a[e.y].x)
			{
				if (a[e.x].y > a[e.y].y)
				{
					a[e.x].l[2] = -1;
					a[e.y].l[0] = -1;
				}
				else
				{
					a[e.x].l[0] = -1;
					a[e.y].l[2] = -1;
				}
			}
			else
			{
				if (a[e.x].x > a[e.y].x)
				{
					a[e.x].l[1] = -1;
					a[e.y].l[3] = -1;
				}
				else
				{
					a[e.x].l[3] = -1;
					a[e.y].l[1] = -1;
				}
			}

			if (degree[e.x] == 0) s.erase (a[e.x]);
			if (degree[e.y] == 0) s.erase (a[e.y]);
		}
	}

	cout << ans.size () << endl;

	for (edge it : ans)
	{
		printf ("%d\n", it.ind + 1);
	}
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:81:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &x, &y);
   ~~~~~~^~~~~~~~~~~~~~~~
flood.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &x, &y);
   ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3832 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 14556 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 14208 KB Output is correct
2 Correct 413 ms 16848 KB Output is correct

Subtask #13
9.0 / 9.0

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

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 16376 KB Output is correct
2 Correct 646 ms 28864 KB Output is correct