Submission #150160

#	Time	Username	Problem	Language	Result	Execution time	Memory
150160		From The Sky (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	122 ms	8800 KiB

island

//subtask K <= 1000
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include "island.h"
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int maxk = 1000 + 5;
const int mlog = 17;
const int inf = 1e8;

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

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

void dfs(int u, int last) {
	//printf("dfs %d %d\n",u,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[par[u][i-1]][i-1], up[u][i-1]);
		//printf("\tup %d %d = %d\n",u,i,up[u][i]);
	}
	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 x, int y) {
	int res = m;
	if(h[x]<h[y]) swap(x,y);
	for(int i=mlog;i>=0;i--) {
		if(h[par[x][i]] >= h[y]) {
			//printf("par = %d\n",par[x][i]);
			//printf("\t*lca <= %d\n",up[x][i]);
			res = min(res, up[x][i]);
			x = par[x][i];
		}
	}
	if(x==y) return res;
	for(int i=mlog;i>=0;i--) {
		if(i == 0 || par[x][i] != par[y][i]) {
			res = min(res, up[x][i]);
			res = min(res, up[y][i]);
			//printf("\tlca <= %d\n",up[x][i]);
			//printf("\tlca <= %d\n",up[y][i]);
			x = par[x][i];
			y = par[y][i];
		}
	}
	return res; 
}

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	n = F.size(); m = S.size(); k = K;
	for(int i=1;i<=n;i++) {
		a[i] = F[i-1];
		have[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) head[i] = i;
	for(int i=m-1;i>=0;i--) {
		S[i]++; E[i]++;
		if(findhead(S[i])!=findhead(E[i])) {
			head[findhead(S[i])] = findhead(E[i]);
			way[S[i]].push_back({E[i], i+1});
			way[E[i]].push_back({S[i], i+1});
			//printf("edge %d %d\n",S[i],E[i]);
		}
	}
	dfs(1,0);
}

int Separate(int A, int B){
	if(have[A].empty() || have[B].empty()) return 0;
	int x = have[A][0], y = have[B][0];
	return lca(x,y);
	//if((int)have[A].size() >= wow) return ans[A][B] + 1;
	//if((int)have[B].size() >= wow) return ans[B][A] + 1;
}

/*

#include <stdio.h>
#include <stdlib.h>

static void my_assert(int TF, const char* message){
	if(!TF){ puts(message); exit(0); }
}

int main(){
	int N, M, K, Q;
	std::vector<int> F, S, E;

	my_assert(scanf("%d%d%d%d", &N, &M, &K, &Q) == 4, "Error: Invalid Input");
	my_assert(1 <= K && K <= N && N <= 300000, "Error: Invalid Input");
	my_assert(N - 1 <= M && M <= 1000000, "Error: Invalid Input");
	my_assert(1 <= Q && Q <= 300000, "Error: Invalid Input");

	for(int i = 0; i < N; i++){
		int a;
		my_assert(scanf("%d", &a) == 1, "Error: Invalid Input");
		my_assert(0 <= a && a < K, "Error: Invalid Input");
		F.push_back(a);
	}
	for(int i = 0; i < M; i++){
		int a, b;
		my_assert(scanf("%d%d", &a, &b) == 2, "Error: Invalid Input");
		my_assert(0 <= a && a < N && 0 <= b && b < N && a != b, "Error: Invalid Input");
		S.push_back(a), E.push_back(b);
	}
	Init(K, F, S, E);

	for(int i = 0; i < Q; i++){
		int a, b;
		my_assert(scanf("%d%d", &a, &b) == 2, "Error: Invalid Input");
		my_assert(0 <= a && a < K && 0 <= b && b < K && a != b, "Error: Invalid Input");
		printf("%d\n", Separate(a, b));
	}
	return 0;
}


*/

Compilation message (stderr)

island.cpp:2:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

• Subtask 1: 0 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30