oj.uz

Submission #150296

# Submission time Handle Problem Language Result Execution time Memory
150296 2019-09-01T08:05:04 Z From The Sky(#3630, WhipppedCream, top34051, zoomswk) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 292 ms 29028 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int mlog = 18;

int n, m, k;
int a[maxn], act[maxn];
int head[maxn];
vector<pair<int,int>> way[maxn];
int h[maxn];
int par[maxn][20], up[maxn][20];

void dfs(int u, int last) {
	h[u] = h[last] + 1;
	for(int i=1;i<=mlog;i++) {
		par[u][i] = par[par[u][i-1]][i-1];
		up[u][i] = min(up[u][i-1], up[par[u][i-1]][i-1]);
	}
	for(auto tmp : way[u]) {
		int v = tmp.first, val = tmp.second;
		if(v == last) continue;
		par[v][0] = u;
		up[v][0] = val;
		dfs(v, u);
	}
}

int lca(int u, int v) {
	int res = m;
	if(h[u] < h[v]) swap(u, v);
	for(int i=mlog;i>=0;i--) {
		if(h[par[u][i]] >= h[v]) {
			res = min(res, up[u][i]);
			u = par[u][i];
		}
	}
	if(u==v) return res;
	for(int i=mlog;i>=0;i--) {
		if(par[u][i] != par[v][i]) {
			res = min(res, min(up[u][i], up[v][i]));
			u = par[u][i];
			v = par[v][i];
		}
	}
	return min(res, min(up[u][0], up[v][0]));
}

int findhead(int x) {
	if(x==head[x]) return x;
	return head[x] = findhead(head[x]);
}

void Init(int K, vector<int> col, vector<int> s, vector<int> e) {
	n = col.size(); m = s.size(); k = K;
	for(int i=1;i<=n;i++) {
		a[i] = col[i-1];
		act[a[i]] = i;
	}
	for(int i=1;i<=n;i++) head[i] = i;
	for(int i=m;i>=1;i--) {
		int x = s[i-1] + 1, y = e[i-1] + 1;
		if(findhead(x) != findhead(y)) {
			head[findhead(x)] = findhead(y);
			way[x].push_back({y, i});
			way[y].push_back({x, i});
		}
	}
	dfs(1,0);
}

int Separate(int x, int y) {
	x = act[x]; y = act[y];
	return lca(x, y);
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 29028 KB Output is correct
2 Correct 273 ms 29028 KB Output is correct
3 Correct 269 ms 29024 KB Output is correct
4 Correct 292 ms 29024 KB Output is correct
5 Correct 269 ms 28896 KB Output is correct
6 Correct 288 ms 29028 KB Output is correct
7 Correct 272 ms 29028 KB Output is correct
8 Correct 262 ms 29028 KB Output is correct
9 Correct 286 ms 29028 KB Output is correct
10 Correct 264 ms 29024 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

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