Submission #530208

#	Time	Username	Problem	Language	Result	Execution time	Memory
530208		luciocf	Colors (RMI18_colors)	C++14	0 / 100	3052 ms	26196 KiB

colors

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 5e5+10;

int a[maxn], b[maxn];
pii p[maxn];

vector<int> quem[maxn];

bool mark[maxn];

vector<int> grafo[maxn];

void dfs(int u, int c)
{
	mark[u] = 1;

	for (auto v: grafo[u])
		if (!mark[v] && b[v] <= c)
			dfs(v, c);
}

bool reach(int u, int v, int c)
{
	memset(mark, 0, sizeof mark);
	dfs(u, c);

	return mark[v];
}

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

	while (tc--)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		for (int i = 1; i <= n; i++)
		{
			grafo[i].clear();
			quem[i].clear();
		}

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

			quem[a[i]].push_back(i);
		}

		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &b[i]);

			p[i] = {b[i], i};
		}

		for (int i = 1; i <= m; i++)
		{
			int u, v;
			scanf("%d %d", &u, &v);

			grafo[u].push_back(v);
			grafo[v].push_back(u);
		}

		sort(p+1, p+n+1);

		bool ok = 1;

		for (int i = n; i >= 1; i--)
		{
			int c = p[i].ff, u = p[i].ss;

			bool flag = 0;

			for (auto v: quem[c])
				if (reach(v, u, c))
					flag = 1;

			ok &= flag;
		}

		if (ok) printf("1\n");
		else printf("0\n");
	}
}

Compilation message (stderr)

colors.cpp: In function 'int main()':
colors.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d", &tc);
      |  ~~~~~^~~~~~~~~~~
colors.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    scanf("%d", &a[i]);
      |    ~~~~~^~~~~~~~~~~~~
colors.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |    scanf("%d", &b[i]);
      |    ~~~~~^~~~~~~~~~~~~
colors.cpp:71:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |    scanf("%d %d", &u, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22