oj.uz

Submission #530224

# Submission time Handle Problem Language Result Execution time Memory
530224 2022-02-24T20:06:48 Z luciocf Colors (RMI18_colors) C++14
63 / 100
 3000 ms 79376 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 5e5+10;
const int inf = 1e9+10;

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

vector<int> quem[maxn];

bool mark[maxn];

vector<int> grafo[maxn];

struct BinaryLifting
{
	int nivel[maxn];
	int tab[maxn][20], mn[maxn][20], mx[maxn][20];

	void dfs(int u, int p)
	{
		for (auto v: grafo[u])
		{
			if (v == p) continue;

			nivel[v] = nivel[u]+1, tab[v][0] = u;
			dfs(v, u);
		}
	}

	void build(void)
	{
		for (int i = 1; i <= n; i++)
		{
			if (tab[i][0] == 0) mx[i][0] = b[i];
			else mx[i][0] = max(b[i], b[tab[i][0]]);
			
			if (tab[i][0] == 0) mn[i][0] = a[i];
			else mn[i][0] = min(a[i], a[tab[i][0]]);
		}

		for (int j = 1; j < 20; j++)
		{
			for (int i = 1; i <= n; i++)
			{
				tab[i][j] = tab[tab[i][j-1]][j-1];
				mx[i][j] = max(mx[i][j-1], mx[tab[i][j-1]][j-1]);
				mn[i][j] = min(mn[i][j-1], mn[tab[i][j-1]][j-1]);
			}
		}
	}

	int get_mn(int u, int v)
	{
		if (nivel[u] < nivel[v]) swap(u, v);

		int ans = inf;

		for (int i = 19; i >= 0; i--)
			if (nivel[u]-(1<<i) >= nivel[v])
				ans = min(ans, mn[u][i]), u = tab[u][i];

		if (u == v) return ans;

		for (int i = 19; i >= 0; i--)
			if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
				ans = min({ans, mn[u][i], mn[v][i]}), u = tab[u][i], v = tab[v][i];

		return min({ans, mn[u][0], mn[v][0]});
	}

	int get_mx(int u, int v)
	{
		if (nivel[u] < nivel[v]) swap(u, v);

		int ans = 0;

		for (int i = 19; i >= 0; i--)
			if (nivel[u]-(1<<i) >= nivel[v])
				ans = max(ans, mx[u][i]), u = tab[u][i];

		if (u == v) return ans;

		for (int i = 19; i >= 0; i--)
			if (tab[u][i] && tab[v][i] && tab[u][i] != tab[v][i])
				ans = max({ans, mx[u][i], mx[v][i]}), u = tab[u][i], v = tab[v][i];

		return max({ans, mx[u][0], mx[v][0]});
	}
} LCA;

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];
}

void solve_tree(void)
{
	bool ok = 1;

	for (int i = 1; i <= n; i++)
		if (a[i] < b[i])
			ok = 0;

	LCA.dfs(1, 0);
	LCA.build();

	for (int u = 1; u <= n; u++)
	{
		int c = b[u];
		bool flag = 0;

		for (auto v: quem[c])
			if (LCA.get_mn(u, v) >= c && LCA.get_mx(u, v) <= c)
				flag = 1;

		ok &= flag;
	}

	printf("%d\n", ok);
}

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

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

		vector<int> bla;

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

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

			bla.push_back(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(bla.begin(), bla.end());

		bool sub_tree = (m == n-1);
		for (int i = 0; i < bla.size(); i++)
			if (bla[i] != i+1)
				sub_tree = 0;

		if (sub_tree)
		{
			solve_tree();
			continue;
		}

		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:187:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |   for (int i = 0; i < bla.size(); i++)
      |                   ~~^~~~~~~~~~~~
colors.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |  scanf("%d", &tc);
      |  ~~~~~^~~~~~~~~~~
colors.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
colors.cpp:162:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |    scanf("%d", &a[i]);
      |    ~~~~~^~~~~~~~~~~~~
colors.cpp:170:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |    scanf("%d", &b[i]);
      |    ~~~~~^~~~~~~~~~~~~
colors.cpp:178:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |    scanf("%d %d", &u, &v);
      |    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1416 ms 24392 KB Output is correct
2 Correct 395 ms 24528 KB Output is correct
3 Correct 118 ms 24688 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 24320 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 24448 KB Output is correct
2 Correct 424 ms 24424 KB Output is correct
3 Correct 90 ms 24700 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1276 ms 24448 KB Output is correct
2 Correct 424 ms 24424 KB Output is correct
3 Correct 90 ms 24700 KB Output is correct
4 Correct 2772 ms 25428 KB Output is correct
5 Execution timed out 3041 ms 42532 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1416 ms 24392 KB Output is correct
2 Correct 395 ms 24528 KB Output is correct
3 Correct 118 ms 24688 KB Output is correct
4 Correct 1276 ms 24448 KB Output is correct
5 Correct 424 ms 24424 KB Output is correct
6 Correct 90 ms 24700 KB Output is correct
7 Correct 1226 ms 24576 KB Output is correct
8 Correct 458 ms 24424 KB Output is correct
9 Correct 18 ms 24212 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 23884 KB Output is correct
2 Correct 345 ms 46608 KB Output is correct
3 Correct 368 ms 79376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 24448 KB Output is correct
2 Correct 86 ms 24488 KB Output is correct
3 Correct 101 ms 24444 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1416 ms 24392 KB Output is correct
2 Correct 395 ms 24528 KB Output is correct
3 Correct 118 ms 24688 KB Output is correct
4 Correct 360 ms 24320 KB Output is correct
5 Correct 1276 ms 24448 KB Output is correct
6 Correct 424 ms 24424 KB Output is correct
7 Correct 90 ms 24700 KB Output is correct
8 Correct 2772 ms 25428 KB Output is correct
9 Execution timed out 3041 ms 42532 KB Time limit exceeded
10 Halted 0 ms 0 KB -