oj.uz

Submission #530209

# Submission time Handle Problem Language Result Execution time Memory
530209 2022-02-24T19:36:10 Z luciocf Colors (RMI18_colors) C++14
7 / 100
 3000 ms 24432 KB 
#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;
		}

		for (int i = 1; i <= n; i++)
			if (a[i] < b[i])
				ok = 0;
			
		if (ok) printf("1\n");
		else printf("0\n");
	}
}

Compilation message

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:72:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |    scanf("%d %d", &u, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2194 ms 24296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 24300 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2401 ms 24284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2401 ms 24284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2194 ms 24296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 24432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 24300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2194 ms 24296 KB Output isn't correct
2 Halted 0 ms 0 KB -