#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define ff first
#define ss second
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &x, T y){
x = min(x,y);
}
template<typename T>
void amax(T &x, T y){
x = max(x,y);
}
template<typename A,typename B>
string to_string(pair<A,B> p);
string to_string(const string &s){
return "'"+s+"'";
}
string to_string(const char* s){
return to_string((string)s);
}
string to_string(bool b){
return b?"true":"false";
}
string to_string(vector<bool> v){
string res = "{";
rep(i,sz(v)){
res += to_string(v[i])+",";
}
if(res.back() == ',') res.pop_back();
res += "}";
return res;
}
template<typename A>
string to_string(A v){
string res = "{";
trav(x,v){
res += to_string(x)+",";
}
if(res.back() == ',') res.pop_back();
res += "}";
return res;
}
template<typename A,typename B>
string to_string(pair<A,B> p){
return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}
#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;
#include "swap.h"
vector<int> par(N);
int find(int u){
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void merge(int u, int v){
u = find(u), v = find(v);
if(u == v) return;
par[v] = u;
}
vector<pii> adj1[N], adj2[N];
vector<int> pedge(N,inf1);
void dfs1(int u, int p){
for(auto [v,w] : adj1[u]){
if(v == p) conts;
pedge[v] = w;
pii px = {u,w};
adj1[v].erase(find(all(adj1[v]),px));
dfs1(v,u);
}
}
int fmn(int u, pii ignore){
int mn = inf1;
for(auto [v,w] : adj2[u]){
if(v == ignore.ff or v == ignore.ss) conts;
amin(mn,w);
}
return mn;
}
const int LOG = 17;
int up[N][LOG], mnw[N][LOG], mxw[N][LOG];
vector<int> depth(N);
void dfs2(int u){
for(auto [v,w] : adj1[u]){
depth[v] = depth[u]+1;
up[v][0] = u;
mnw[v][0] = fmn(u,{v,-1});
mxw[v][0] = w;
rep1(j,LOG-1){
up[v][j] = up[up[v][j-1]][j-1];
mnw[v][j] = min(mnw[v][j-1],mnw[up[v][j-1]][j-1]);
mxw[v][j] = max(mxw[v][j-1],mxw[up[v][j-1]][j-1]);
}
dfs2(v);
}
}
int lift(int u, int k){
rep(j,LOG){
if(k&(1<<j)){
u = up[u][j];
}
}
return u;
}
int get_lca(int u, int v){
if(depth[u] < depth[v]) swap(u,v);
int k = depth[u]-depth[v];
u = lift(u,k);
if(u == v) return u;
rev(j,LOG-1,0){
if(up[u][j] != up[v][j]){
u = up[u][j];
v = up[v][j];
}
}
u = up[u][0], v = up[v][0];
assert(u == v);
return u;
}
int get_mn(int u, int k){
if(k < 0) return inf1;
int mn = inf1;
rep(j,LOG){
if(k&(1<<j)){
amin(mn,mnw[u][j]);
u = up[u][j];
}
}
return mn;
}
int get_mx(int u, int k){
int mx = -inf1;
rep(j,LOG){
if(k&(1<<j)){
amax(mx,mxw[u][j]);
u = up[u][j];
}
}
return mx;
}
void init(int n, int m,
std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<array<int,3>> edges;
rep(i,m){
edges.pb({W[i],U[i],V[i]});
}
sort(all(edges));
vector<array<int,3>> span, non_span;
iota(all(par),0);
for(auto [w,u,v] : edges){
if(find(u) != find(v)){
span.pb({u,v,w});
merge(u,v);
}
else{
non_span.pb({u,v,w});
}
}
for(auto [u,v,w] : span){
adj1[u].pb({v,w}), adj1[v].pb({u,w});
}
for(auto [u,v,w] : non_span){
adj2[u].pb({v,w}), adj2[v].pb({u,w});
}
dfs1(0,-1);
rep(u,n){
for(auto [v,w] : adj1[u]){
adj2[u].pb({v,w});
}
sort(all(adj1[u]));
sort(all(adj2[u]));
}
rep(j,LOG) mnw[0][j] = inf1;
dfs2(0);
}
int getMinimumFuelCapacity(int u, int v) {
if(depth[u] > depth[v]) swap(u,v);
int lca = get_lca(u,v);
int du = depth[u]-depth[lca];
int dv = depth[v]-depth[lca];
int pmx = max(get_mx(u,du),get_mx(v,dv));
int mn = inf1;
amin(mn,get_mn(u,du-1));
amin(mn,get_mn(v,dv-1));
if(u == lca){
// int jb = lift(v,dv-1);
// amin(mn,fmn(u,{jb,-1}));
}
else{
amin(mn,fmn(u,{-1,-1}));
int jbu = lift(u,du-1), jbv = lift(v,dv-1);
amin(mn,fmn(lca,{jbu,jbv}));
amin(mn,pedge[lca]);
}
amin(mn,fmn(v,{-1,-1}));
int ans = max(pmx,mn);
if(ans == inf1) ans = -1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6216 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Execution timed out |
2082 ms |
27504 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6216 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6216 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6216 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6236 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
6216 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
