oj.uz

Submission #150554

# Submission time Handle Problem Language Result Execution time Memory
150554 2019-09-01T08:38:07 Z 1 WA = 5 Push Up(#3624, BaaaaaaaaaaaaaaaarkingDog, IohcEjnim, 0xrgb) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 330 ms 36576 KB 
#include "island.h"
//#include "header.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define X first
#define Y second

int isl[100010];
int p[100010];

int unf(int a) { return p[a] = (a == p[a]) ? a : unf(p[a]); }

class LCA { // 1-indexed 
public:
	vector < vector< pair<int, int> > > adj;
	vector< vector<int> > anc, minv; // anc[i][j] : 2**j-th ancestor of i
	vector<int> depth;
	int n, mxdepth;
	LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
		mxdepth = 20;
		for (int i = 0; i <= n; i++) anc[i].resize(mxdepth);
		for (int i = 0; i <= n; i++) minv[i].resize(mxdepth);
	}
	void construct(int cur, int p, int v) {
		depth[cur] = depth[p] + 1;
		anc[cur][0] = p;
		minv[cur][0] = v;
		for (int i = 1; i < mxdepth; i++)
		{
			anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
			minv[cur][i] = min(minv[cur][i - 1], minv[anc[cur][i - 1]][i - 1]);
		}
		for (auto n : adj[cur]) {
			if (n.X != p) construct(n.X, cur, n.Y);
		}
	}
	void construct(int root) { // set anc table
		construct(root, 0, 0);
	}
	int lca(int a, int b) { // returns lca of a,b
		if (depth[a] > depth[b]) swap(a, b);
		int ret = 0x7f7f7f7f;
		for (int i = mxdepth - 1; i >= 0; i--) {
			if (depth[a] <= depth[anc[b][i]])
			{
				ret = min(ret, minv[b][i]);
				b = anc[b][i];
			}

		}
		if (a != b) {
			for (int j = mxdepth - 1; j >= 0; j--) {
				if (anc[a][j] != 0 and anc[a][j] != anc[b][j]) {
					ret = min(ret, min(minv[a][j], minv[b][j]));
					a = anc[a][j];
					b = anc[b][j];
				}
			}
			ret = min(ret, min(minv[a][0], minv[b][0]));
		}
		return ret;
	}
	void pushadj(int a, int b, int v) {
		adj[a].pb({ b, v });
		adj[b].pb({ a, v });
	}
};

LCA* lca;

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E) {
	int N = F.size(), M = S.size();
	lca = new LCA(N);

	for (int i = 0; i < M; i++)
		S[i]++, E[i]++;
	
	for (int i = 0; i < N; i++)
		isl[F[i]] = i + 1;

	for (int i = 1; i <= N; i++) p[i] = i;
	for (int i = M - 1; i >= 0; i--)
	{
		int a = S[i], b = E[i];
		a = unf(a); b = unf(b);

		if (a == b) continue;
		lca->pushadj(S[i], E[i], i);

		p[b] = a;
	}

	lca->construct(N / 2 + 1);
}

int Separate(int A, int B) {
	A = isl[A]; B = isl[B];
	return lca->lca(A, B) + 1;
}

/*
5 6 5 3
0 1 2 3 4
0 1
2 3
2 4
4 3
1 2
0 4
*/

Compilation message

island.cpp: In constructor 'LCA::LCA(int)':
island.cpp:21:6: warning: 'LCA::n' will be initialized after [-Wreorder]
  int n, mxdepth;
      ^
island.cpp:18:38: warning:   'std::vector<std::vector<std::pair<int, int> > > LCA::adj' [-Wreorder]
  vector < vector< pair<int, int> > > adj;
                                      ^~~
island.cpp:22:2: warning:   when initialized here [-Wreorder]
  LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
  ^~~
island.cpp:20:14: warning: 'LCA::depth' will be initialized after [-Wreorder]
  vector<int> depth;
              ^~~~~
island.cpp:19:24: warning:   'std::vector<std::vector<int> > LCA::anc' [-Wreorder]
  vector< vector<int> > anc, minv; // anc[i][j] : 2**j-th ancestor of i
                        ^~~
island.cpp:22:2: warning:   when initialized here [-Wreorder]
  LCA(int n) :n(n), adj(n + 1), depth(n + 1), anc(n + 1), minv(n + 1) {
  ^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 36452 KB Output is correct
2 Correct 305 ms 36448 KB Output is correct
3 Correct 316 ms 36448 KB Output is correct
4 Correct 306 ms 36452 KB Output is correct
5 Correct 292 ms 36452 KB Output is correct
6 Correct 330 ms 36448 KB Output is correct
7 Correct 329 ms 36452 KB Output is correct
8 Correct 308 ms 36576 KB Output is correct
9 Correct 309 ms 36576 KB Output is correct
10 Correct 309 ms 36576 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

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