#define wiwihorz
#include "swap.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define all(x) x.begin(), x.end()
#define ll long long int
#define pii pair<int, int>
#define INF 2000000000
using namespace std;
#ifdef wiwihorz
#define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a)
void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
vector<vector<int>> ac, mx, mn;
vector<vector<pii>> v, mp;
vector<int> dep;
int lg;
void dfs(int x, int par, int d, int es, int val) {
ac[0][x] = par;
mx[0][x] = es;
mn[0][x] = val;
dep[x] = d;
vector<pii> tp;
if(x != par) tp.push_back({es, par});
for(auto i : mp[x]) if(i.x != par) {
tp.push_back({i.y, i.x});
}
sort(all(tp));
rep(i, 0, min(signed(tp.size()), 3) - 1) v[x][i] = tp[i];
for(auto i : mp[x]) if(i.x != par) {
int ii = 0;
while(ii < 3 && (v[x][ii].y == i.x || v[x][ii].y == par)) ii++;
assert(ii < 3);
dfs(i.x, x, d + 1, i.y, v[x][ii].x);
}
}
int LCA(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
int need = dep[a] - dep[b];
rep(i, 0, lg) if((need >> i) & 1) {
a = ac[i][a];
}
if(a == b) return a;
rrep(i, 0, lg) if(ac[i][a] != ac[i][b]) {
a = ac[i][a];
b = ac[i][b];
}
return ac[0][a];
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
lg = 31 - __builtin_clz(N);
mp.assign(N, vector<pii>());
ac.assign(lg + 1, vector<int>(N, 0));
mx.assign(lg + 1, vector<int>(N, 0));
mn.assign(lg + 1, vector<int>(N, INF));
v.assign(N, vector<pii>(3, {INF, 0}));
dep.assign(N, 0);
rep(i, 0, M - 1) {
mp[U[i]].push_back({V[i], W[i]});
mp[V[i]].push_back({U[i], W[i]});
}
dfs(0, 0, 0, 0, INF);
rep(i, 1, lg) rep(j, 0, N - 1) {
ac[i][j] = ac[i - 1][ac[i - 1][j]];
mx[i][j] = max(mx[i - 1][j], mx[i - 1][ac[i - 1][j]]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][ac[i - 1][j]]);
}
return;
}
int go(int a, int x, int tp) {
if(tp == 1) {
int ans = 0;
if(x < 0) return INF;
rep(i, 0, lg) if((x >> i) & 1) {
ans = max(ans, mx[i][a]);
a = ac[i][a];
}
return ans;
}
else {
int ans = INF;
if(x < 0) return INF;
rep(i, 0, lg) if((x >> i) & 1) {
ans = min(ans, mn[i][a]);
a = ac[i][a];
}
return ans;
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(dep[X] < dep[Y]) swap(X, Y);
int lca = LCA(X, Y);
if(lca == Y) {
int need = dep[X] - dep[Y];
int L = go(X, need, 1);
int R = go(X, need - 1, 0);
return max(L, R) == INF ? -1 : max(L, R);
}
else {
int l = dep[X] - dep[lca];
int r = dep[Y] - dep[lca];
int L = max(go(X, l, 1), go(Y, r, 1));
int R = min(go(X, l - 1, 0), go(Y, r - 1, 0));
int ii = 0, x = X, y = Y;
rep(i, 0, lg) if(((l - 1) >> i) & 1) x = ac[i][x];
rep(i, 0, lg) if(((r - 1) >> i) & 1) y = ac[i][y];
while(ii < 3 && (v[lca][ii].y == x || v[lca][ii].y == y)) ii ++;
assert(ii != 3);
R = min(R, v[lca][ii].x);
return max(L, R) == INF ? -1 : max(L, R);
}
}
Compilation message
swap.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
6 | #pragma loop-opt(on)
|
swap.cpp:16:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
swap.cpp:16:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
