#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,a,b,k;
ll lab[maxN],val[maxN],sz[maxN],cnt=0;
void build()
{
cnt=0;
for(int i=1;i<=n+a+b;i++) lab[i]=-1,val[i]=0;
for(int i=1;i<=n;i++) sz[i]=1;
}
struct Tedge
{
ll u,v,w;
bool operator<(const Tedge&o)
{
return w<o.w;
}
}e[maxN],f[maxN];
ll findset(ll x)
{
return lab[x]<0?x:lab[x]=findset(lab[x]);
}
bool unite(ll u,ll v)
{
u=findset(u);
v=findset(v);
if(u==v) return false;
if(lab[u]>lab[v]) swap(u,v);
cnt-=val[u];
cnt-=val[v];
val[u]=val[u]+val[v]+sz[u]*sz[v];
sz[u]+=sz[v];
lab[u]+=lab[v];
cnt+=val[u];
lab[v]=u;
return true;
}
vector<pli>g[maxN];
bool vis[maxN];
ll P[maxN][20],mx[maxN][20],h[maxN];
void dfs(ll u,ll p)
{
P[u][0]=p;
vis[u]=true;
for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
for(int i=1;i<=18;i++) mx[u][i]=max(mx[u][i-1],mx[P[u][i-1]][i-1]);
for(auto vv:g[u])
{
if(vv.fi!=p)
{
h[vv.fi]=h[u]+1;
mx[vv.fi][0]=vv.se;
dfs(vv.fi,u);
}
}
}
ll lca(ll u,ll v)
{
if(h[u]<h[v]) swap(u,v);
for(int i=18;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
if(u==v) return u;
for(int i=18;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
return P[u][0];
}
ll pth(ll u,ll v)
{
ll k=h[u]-h[v];
ll aa=0;
for(int i=18;i>=0;i--)
{
if(k>>i&1)
{
aa=max(aa,mx[u][i]);
u=P[u][i];
}
}
return aa;
}
ll get(ll u,ll v)
{
ll x=lca(u,v);
if(x==0) return max(a,b)+1;
return max(pth(u,x),pth(v,x));
}
struct qq
{
ll t,id,w,u,v;
bool operator<(const qq&o)
{
if(w==o.w) return t<o.t;
return w<o.w;
}
};
vector<qq>edge;
ll suma[maxN],sumb[maxN];
void solve()
{
cin >> n >> a >> b >> k;
build();
for(int i=1;i<=a;i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e+1,e+a+1);
for(int i=1;i<=a;i++)
{
if(unite(e[i].u,e[i].v))
{
g[e[i].u].pb({e[i].v,i});
g[e[i].v].pb({e[i].u,i});
}
}
for(int i=1;i<=n;i++) vis[i]=false;
h[0]=-1;
for(int i=1;i<=n;i++)
{
if(vis[i]==false)
{
dfs(i,0);
}
}
for(int i=1;i<=b;i++)
{
cin >> f[i].u >> f[i].v >> f[i].w;
}
sort(f+1,f+b+1);
for(int i=1;i<=b;i++)
{
ll x=get(f[i].u,f[i].v);
if(x>a) continue;
edge.pb({0,i,f[i].w,f[i].u,n+i});
edge.pb({0,x,e[x].w,n+i,f[i].v});
}
build();
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=b;i++)
{
if(unite(f[i].u,f[i].v))
{
g[f[i].u].pb({f[i].v,i});
g[f[i].v].pb({f[i].u,i});
}
}
for(int i=1;i<=n;i++)
{
vis[i]=false,h[i]=0;
for(int j=0;j<=18;j++) P[i][j]=0,mx[i][j]=0;
}
h[0]=-1;
for(int i=1;i<=n;i++)
{
if(vis[i]==false)
{
dfs(i,0);
}
}
// cout <<mx[2][0]<<' '<<get(2,6)<<'\n';
for(int i=1;i<=a;i++)
{
ll x=get(e[i].u,e[i].v);
if(x>b) continue;
edge.pb({0,i,e[i].w,e[i].u,b+n+i});
edge.pb({0,x,f[x].w,n+i+b,e[i].v});
//cout << e[i].w<<' '<<f[x].w<<'\n';
}
for(int i=1;i<=a;i++) edge.pb({1,i,e[i].w,n,n});
for(int i=1;i<=b;i++) edge.pb({2,i,f[i].w,n,n});
sort(edge.begin(),edge.end());
build();
for(int i=1;i<=a;i++)
{
unite(e[i].u,e[i].v);
suma[i]=cnt;
//cout << suma[i]<< ' ';
}
build();
for(int i=1;i<=b;i++)
{
unite(f[i].u,f[i].v);
sumb[i]=cnt;
//cout<< sumb[i]<<' ';
}
build();
ll id1=0,id2=0;
ll ans=-1;
ll kind;
for(int i=0;i<edge.size();i++)
{
unite(edge[i].u,edge[i].v);
if(edge[i].t==2)
{
id2=edge[i].id;
}
else if(edge[i].t==1)
{
id1=edge[i].id;
}
if(suma[id1]+sumb[id2]-cnt>=k)
{
ans=edge[i].w;
kind=edge[i].t;
break;
}
}
if(ans==-1)
{
cout << ans;
return;
}
build();
id1=0,id2=0;
for(int i=0;i<edge.size();i++)
{
if(edge[i].t==kind)
{
unite(edge[i].u,edge[i].v);
id2=edge[i].id;
}
if(edge[i].w>ans) break;
}
for(int i=0;i<edge.size();i++)
{
if(edge[i].t!=kind)
{
unite(edge[i].u,edge[i].v);
id1=edge[i].id;
if(suma[id1]+sumb[id2]-cnt>=k)
{
cout << ans+edge[i].w;
break;
}
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:198:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i=0;i<edge.size();i++)
| ~^~~~~~~~~~~~
Main.cpp:223:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int i=0;i<edge.size();i++)
| ~^~~~~~~~~~~~
Main.cpp:232:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
232 | for(int i=0;i<edge.size();i++)
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
335 ms |
124232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23892 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
23828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
