oj.uz

Submission #530211

# Submission time Handle Problem Language Result Execution time Memory
530211 2022-02-24T19:43:31 Z luciocf Colors (RMI18_colors) C++14
47 / 100
 3000 ms 26440 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] && a[v] >= c && 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2324 ms 24296 KB Output is correct
2 Correct 746 ms 24776 KB Output is correct
3 Correct 158 ms 24460 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 24292 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2295 ms 24280 KB Output is correct
2 Correct 893 ms 24948 KB Output is correct
3 Correct 117 ms 24420 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2295 ms 24280 KB Output is correct
2 Correct 893 ms 24948 KB Output is correct
3 Correct 117 ms 24420 KB Output is correct
4 Execution timed out 3077 ms 26440 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2324 ms 24296 KB Output is correct
2 Correct 746 ms 24776 KB Output is correct
3 Correct 158 ms 24460 KB Output is correct
4 Correct 2295 ms 24280 KB Output is correct
5 Correct 893 ms 24948 KB Output is correct
6 Correct 117 ms 24420 KB Output is correct
7 Correct 2305 ms 25684 KB Output is correct
8 Correct 949 ms 24912 KB Output is correct
9 Correct 132 ms 24440 KB Output is correct

Subtask #6
0 / 16.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 24304 KB Output is correct
2 Correct 99 ms 24568 KB Output is correct
3 Correct 101 ms 24460 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2324 ms 24296 KB Output is correct
2 Correct 746 ms 24776 KB Output is correct
3 Correct 158 ms 24460 KB Output is correct
4 Correct 363 ms 24292 KB Output is correct
5 Correct 2295 ms 24280 KB Output is correct
6 Correct 893 ms 24948 KB Output is correct
7 Correct 117 ms 24420 KB Output is correct
8 Execution timed out 3077 ms 26440 KB Time limit exceeded
9 Halted 0 ms 0 KB -