oj.uz

답안 #109104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109104 2019-05-04T11:09:43 Z MetB Flood (IOI07_flood) C++14
26 / 100
 2000 ms 24976 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];

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

struct edge
{
	int x, y, ind;

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

} b[200000];

int degree[100000], n, w;

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

map <int, int> g[100000];

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

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

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

		pos = new_pos;

		edge k = b[g[min (f, a[f].l[pos])][max (f, a[f].l[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};
	}

	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);

		g[x][y] = i;

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

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

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

	while (!s.empty ())
	{
		point corner = *s.rbegin ();

		ccw (corner.ind);

		for (auto e : to_erase)
		{
			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:83: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:93: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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5120 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5120 KB Output isn't correct

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2028 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4992 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB Output is correct

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2092 ms 9208 KB Time limit exceeded

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2059 ms 20320 KB Time limit exceeded

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2032 ms 20240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2051 ms 24028 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2027 ms 24976 KB Time limit exceeded
2 Halted 0 ms 0 KB -