Submission #241275

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241275	2020-06-23T13:32:55 Z	luciocf	Mostovi (COI14_mostovi)	C++14	10 / 100	243 ms	12408 KB

mostovi

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

set<int> st_up, st_down;
set<pii> bridge_up, bridge_down;

// u < v
bool reach_up(int u, int v)
{
	if (u == v) return true;

	auto it = st_up.lower_bound(u);

	return (it == st_up.end() || *it >= v);
}

// u > v
bool reach_down(int u, int v)
{
	if (u == v) return true;

	auto it = st_down.upper_bound(u);

	if (it == st_down.begin()) return true;

	--it;
	return (*it <= v);
}

bool reach_updown(int u, int v)
{
	auto it = bridge_up.lower_bound({u, -1});

	if (it == bridge_up.end()) return false;

	if (!reach_up(u, it->ff) || (it->ss > v && !reach_down(it->ss, v))) return false;

	if (it->ss >= v) return true;

	auto it2 = bridge_down.lower_bound({v, -1});

	if (it2 == bridge_down.end() || !reach_down(it2->ff, v)) return false;

	return (it2->ss >= u && reach_up(u, it2->ss));
}

bool reach_downup(int u, int v)
{
	auto it = bridge_down.upper_bound({u, 1e9+10});

	if (it == bridge_down.begin()) return false;
	--it;

	if (!reach_down(it->ff, u) || (it->ss < v && !reach_up(it->ss, v))) return false;

	if (it->ss <= v) return true;

	auto it2 = bridge_up.upper_bound({v, 1e9+10});

	if (it2 == bridge_up.begin()) return false;
	--it2;

	if (!reach_up(it2->ff, v)) return false;

	return (it2->ss <= u && reach_down(u, it2->ss));
}

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	while (m--)
	{
		char op;
		int u, v;
		scanf(" %c %d %d", &op, &u, &v);

		if (op == 'A')
		{
			if (u > v) swap(u, v);

			bridge_up.insert({u, v});
			bridge_down.insert({v, u});
		}
		else if (op == 'B')
		{
			if (u > v) swap(u, v);

			if (u <= n) st_up.insert({u, v});
			else st_down.insert({v, u});
		}
		else
		{
			bool ok;

			if (u <= n && v <= n)
			{
				if (u <= v) ok = reach_up(u, v);
				else
				{
					auto it = bridge_up.lower_bound({u, -1});

					if (it == bridge_up.end()) ok = false;
					else ok = reach_downup(it->ss, v);
				}
			}
			else if (u > n && v > n)
			{
				if (u >= v) ok = reach_down(u, v);
				else
				{
					auto it = bridge_down.upper_bound({u, 1e9+10});

					if (it == bridge_down.begin()) ok = false;
					else
					{
						--it;
						ok = reach_updown(it->ss, v);
					}
				}
			}
			else
			{
				if (u < v) ok = reach_updown(u, v);
				else ok = reach_downup(u, v);
			}

			if (ok) printf("DA\n");
			else printf("NE\n");
		}
	}
}

Compilation message

mostovi.cpp: In function 'int main()':
mostovi.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
mostovi.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d", &op, &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	384 KB	Output isn't correct
2	Incorrect	5 ms	384 KB	Output isn't correct
3	Incorrect	6 ms	384 KB	Output isn't correct
4	Incorrect	5 ms	384 KB	Output isn't correct
5	Correct	5 ms	384 KB	Output is correct
6	Incorrect	5 ms	384 KB	Output isn't correct
7	Incorrect	226 ms	11000 KB	Output isn't correct
8	Incorrect	242 ms	10872 KB	Output isn't correct
9	Incorrect	234 ms	12296 KB	Output isn't correct
10	Incorrect	243 ms	12408 KB	Output isn't correct