Submission #150205

#	Time	Username	Problem	Language	Result	Execution time	Memory
150205		Powered By Zigui (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	784 ms	43512 KiB

island

#include "island.h"
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
#define ARR(...) vector<int>({__VA_ARGS__})
#define ARS(...) vector<string>({__VA_ARGS__})
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef complex<double> base;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const set<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

const int MAXN = 500000;

int K, N, M, X;
int root[MAXN];
int par[MAXN];
int dep[MAXN];
int _lca[MAXN][20];
int minv[MAXN];

int find(int p) {return root[p]==p?p:root[p]=find(root[p]);}

void connect(int a, int b, int v) {
	a = find(a), b = find(b);
	if (a != b) {
		int num = X++;
		root[a] = par[a] = num;
		root[b] = par[b] = num;
		minv[num] = v;
	}
}

void Init(int KK, vector<int> F, vector<int> S, vector<int> E){
	K = KK, N = F.size(), M = S.size(), X = K+N+1;
	debug(X);
	rep(i, MAXN) root[i] = i;
	repr(i, M, 0) {
		connect(S[i]+1, E[i]+1, i+1);
		connect(N+F[S[i]]+1, E[i]+1, i+1);
		connect(S[i]+1, N+F[E[i]]+1, i+1);
	}
	
	repr(i, X, 1) {
		dep[i] = dep[par[i]]+1;
		_lca[i][0] = par[i];
		repp(j, 1, 20) _lca[i][j] = _lca[_lca[i][j-1]][j-1];	
	}
	
	rep(i, X) debug(i, _lca[i][1], minv[i]);
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);
	
	int dif = dep[b]-dep[a];
	rep(i, 20) if (dif&(1<<i)) b = _lca[b][i];
	
	
	if (a == b) return a;
	repr(i, 20, 0) if (_lca[a][i] != _lca[b][i]) a = _lca[a][i], b = _lca[b][i];
	
	return _lca[a][0];
}

int Separate(int A, int B){
	debug(lca(6, 7));
	int a = A+N+1, b = B+N+1;
	
	int p = lca(a, b);
	return minv[p];
}

Compilation message (stderr)

island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:102:10: warning: statement has no effect [-Wunused-value]
  debug(X);
          ^
island.cpp:116:41: warning: statement has no effect [-Wunused-value]
  rep(i, X) debug(i, _lca[i][1], minv[i]);
                                         ^
island.cpp: In function 'int Separate(int, int)':
island.cpp:133:18: warning: statement has no effect [-Wunused-value]
  debug(lca(6, 7));
                  ^

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