oj.uz

Submission #522282

# Submission time Handle Problem Language Result Execution time Memory
522282 2022-02-04T13:26:12 Z blue I want to be the very best too! (NOI17_pokemonmaster) C++17
16 / 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);
				// cerr << i << " : " << crt << '\n';

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

			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 Correct 3197 ms 16812 KB Output is correct
2 Correct 2107 ms 17400 KB Output is correct
3 Correct 959 ms 17396 KB Output is correct
4 Correct 650 ms 17408 KB Output is correct
5 Correct 1980 ms 17396 KB Output is correct
6 Execution timed out 5084 ms 17320 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 15880 KB Output is correct
2 Correct 49 ms 16660 KB Output is correct
3 Correct 38 ms 16644 KB Output is correct
4 Correct 49 ms 17028 KB Output is correct
5 Correct 53 ms 16956 KB Output is correct
6 Correct 84 ms 16868 KB Output is correct
7 Correct 64 ms 15288 KB Output is correct
8 Correct 70 ms 15308 KB Output is correct
9 Correct 85 ms 15316 KB Output is correct
10 Correct 77 ms 15316 KB Output is correct
11 Correct 89 ms 15316 KB Output is correct
12 Correct 83 ms 15760 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3197 ms 16812 KB Output is correct
2 Correct 2107 ms 17400 KB Output is correct
3 Correct 959 ms 17396 KB Output is correct
4 Correct 650 ms 17408 KB Output is correct
5 Correct 1980 ms 17396 KB Output is correct
6 Execution timed out 5084 ms 17320 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3197 ms 16812 KB Output is correct
2 Correct 2107 ms 17400 KB Output is correct
3 Correct 959 ms 17396 KB Output is correct
4 Correct 650 ms 17408 KB Output is correct
5 Correct 1980 ms 17396 KB Output is correct
6 Execution timed out 5084 ms 17320 KB Time limit exceeded
7 Halted 0 ms 0 KB -