oj.uz

Submission #522281

# Submission time Handle Problem Language Result Execution time Memory
522281 2022-02-04T13:23:35 Z blue I want to be the very best too! (NOI17_pokemonmaster) C++17
0 / 100
 5000 ms 17408 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
using vpii = vector<pii>;

const int mx = 50'000;
const int lg = 16;

#define sz(x) int(x.size())

int R, C, Q;
int N;

vi L(mx), P(mx);

vi edge[mx];

void add_edge(int u, int v)
{
	edge[u].push_back(v);
	edge[v].push_back(u);
}









struct disjoint_set
{
	vi parent = vi(mx);
	vi subtree = vi(mx, 1);
	vpii peak = vpii(mx);

	disjoint_set()
	{
		for(int i = 0; i < mx; i++) 
		{
			parent[i] = i;
			peak[i] = {L[i], i};
		}

	}

	int root(int u)
	{
		if(parent[u] == u) return u;
		else return (parent[u] = root(parent[u]));
	}

	int getpeak(int u)
	{
		return peak[root(u)].second;
	}

	void join(int u, int v)
	{
		u = root(u);
		v = root(v);

		if(u == v) return;

		if(subtree[u] < subtree[v]) swap(u, v);

		parent[v] = u;
		subtree[u] += subtree[v];
		peak[u] = max(peak[u], peak[v]);
	}

	bool connected(int u, int v)
	{
		return root(u) == root(v);
	}
};








vi reach_children[mx];
vi reach_parent(mx);

vvi anc(mx, vi(1+lg));

vi subtree(mx, 1);
vi ord;
vi ord_index(mx, -1);
vi depth(mx, 0);

int o_ct = -1;


void dfs(int u)
{
	ord.push_back(u);
	ord_index[u] = ++o_ct;

	for(int v : reach_children[u])
	{
		depth[v] = depth[u] + 1;
		dfs(v);
		subtree[u] += subtree[v];
	}
}

int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1 << e))
			u = anc[u][e];

	return u;
}

int lca(int u, int v)
{
	if(depth[u] > depth[v]) swap(u, v);
	v = ancestor(v, depth[v] - depth[u]);

	if(u == v) return u;

	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] != anc[v][e])
		{
			u = anc[u][e];
			v = anc[v][e];
		}
	}

	return anc[u][0];
}












int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> R >> C >> Q;
	N = R * C;

	for(int i = 0; i < N; i++) cin >> L[i];

	for(int i = 0; i < N; i++) cin >> P[i];

	for(int r = 0; r < R-1; r++)
		for(int c = 0; c < C; c++)
			add_edge(C*r + c, C*(r+1) + c);

	for(int r = 0; r < R; r++)
		for(int c = 0; c < C-1; c++)
			add_edge(C*r + c, C*r + (c+1));












	vpii ord;
	for(int i = 0; i < N; i++)
		ord.push_back({L[i], i});

	sort(ord.begin(), ord.end());

	disjoint_set DS;




	for(int i = 0; i < N; i++)
		reach_parent[i] = i;

	int rt;

	for(auto up: ord)
	{
		int u = up.second;

		rt = u;

		for(int v: edge[u])
		{
			if(L[v] >= L[u]) continue;

			if(DS.connected(u, v)) continue;

			int pu = DS.getpeak(u);
			int pv = DS.getpeak(v);

			reach_parent[pv] = pu;
			reach_children[pu].push_back(pv);

			DS.join(u, v);
		}
	}

	for(int i = 0; i < N; i++)
		anc[i][0] = reach_parent[i];

	for(int e = 1; e <= lg; e++)
		for(int i = 0; i < N; i++)
			anc[i][e] = anc[ anc[i][e-1] ][e-1];

	dfs(rt);





	// for(int i = 0; i < N; i++) cerr << reach_parent[i] << ' ';
	// 	cerr << '\n';



	for(int j = 0; j < Q; j++)
	{
		int T;
		cin >> T;

		if(T == 1)
		{
			int x, y, p;
			cin >> x >> y >> p;

			x--;
			y--;

			int z = C*y + x;

			P[z] = p;
		}
		else
		{
			int x, y, l;
			cin >> x >> y >> l;

			x--;
			y--;

			set<int> res;

			int z = C*y + x;

			// cerr << "z = " << z << '\n';

			for(int i = 0; i < N; i++)
			{
				int crt = lca(i, z);

				if(L[crt] <= l)
					res.insert(P[crt]);
			}

			cout << sz(res) << '\n';
		}
	}
}

Compilation message

pokemonmaster.cpp: In function 'int main()':
pokemonmaster.cpp:233:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  233 |  dfs(rt);
      |  ~~~^~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 29.0

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