Submission #150205

#TimeUsernameProblemLanguageResultExecution timeMemory
150205Powered By Zigui (#200)Trip to the Galapagos Islands (FXCUP4_island)C++17
31 / 100
784 ms43512 KiB
#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));
                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...