Submission #241146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241146	2020-06-23T03:00:44 Z	luciocf	Mostovi (COI14_mostovi)	C++14	0 / 100	253 ms	14460 KB

mostovi

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int n;

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

pii get_up(int u)
{
	int l, r;

	auto it = st_up.lower_bound(u);

	if (it == st_up.end()) r = n;
	else r = *it;

	if (it == st_up.begin()) l = 1;
	else
	{
		--it;
		l = *it + 1;
	}

	return {l, r};
}

pii get_down(int u)
{
	int l, r;

	auto it = st_down.lower_bound(u);

	if (it == st_down.end()) r = 2*n;
	else r = *it - 1;

	it = st_down.upper_bound(u);

	if (it == st_down.begin()) l = n+1;
	else
	{
		--it;
		l = *it;
	}

	return {l, r};
}

// u < v
bool reach_up(int u, int v)
{
	auto it = st_up.lower_bound(u);

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

// u > v
bool reach_down(int u, int v)
{
	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)
{
	pii p1 = get_up(u), p2 = get_down(u);
	int r1 = p1.second, r2 = p2.second;

	auto it = bridge_up.lower_bound({u, -1});

	if (it != bridge_up.end() && it->first <= r1 && it->second >= v && it->second <= r2) return true;

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

	if (it2 != bridge_down.end() && it2->first <= r2 && it2->second >= u && it2->second <= r1) return true;

	return false;
}

bool reach_downup(int u, int v)
{
	pii p1 = get_up(u), p2 = get_down(u);
	int l1 = p1.first, l2 = p2.first;

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

	if (it != bridge_down.begin())
	{
		--it;

		if (it->first >= l2 && it->second <= v && it->second >= l1) return true;
	}

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

	if (it2 != bridge_up.begin())
	{
		--it2;

		if (it2->first >= l1 && it2->second <= u && it2->second >= l2) return true;
	}

	return false;
}

int main(void)
{
	int 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 > n) swap(u, v);

			bridge_up.insert({u, v});
			bridge_down.insert({v, u});
		}
		else if (op == 'B')
		{
			if (u <= n)
				st_up.insert(min(u, v));
			else
				st_down.insert(max(u, v));
		}
		else
		{
			if (u <= n && v <= n)
			{
				if (u > v) swap(u, v);

				if (reach_up(u, v)) printf("DA\n");
				else printf("NE\n");
			}
			else if (u > n && v > n)
			{
				if (u < v) swap(u, v);

				if (reach_down(u, v)) printf("DA\n");
				else printf("NE\n");
			}
			else
			{
				bool ok;

				if (u > v) ok = reach_downup(u, v);
				else ok = reach_updown(u, v);

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

Compilation message

mostovi.cpp: In function 'int main()':
mostovi.cpp:116: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:122: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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	256 KB	Output isn't correct
2	Incorrect	5 ms	384 KB	Output isn't correct
3	Incorrect	5 ms	384 KB	Output isn't correct
4	Incorrect	5 ms	384 KB	Output isn't correct
5	Incorrect	5 ms	384 KB	Output isn't correct
6	Incorrect	5 ms	384 KB	Output isn't correct
7	Incorrect	253 ms	12152 KB	Output isn't correct
8	Incorrect	187 ms	12152 KB	Output isn't correct
9	Incorrect	192 ms	12152 KB	Output isn't correct
10	Incorrect	231 ms	14460 KB	Output isn't correct