#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define rep(i,n) for(ll i = 1; i <= n; i++)
ll n,na,nb,k,w,sum,p[200010],ngs[200010];
pair<ll,ii> d[200010], dd[200010];
vector<ll> adj[200010],adjl[200010];
set<ll> s,ss;
map<ll,ll> m,mm;
ll find(ll x){
ll ind= *upper_bound(s.begin(), s.end(), x);
return m[ind];
}
ll par(ll x) { return (p[x]==x)? x:p[x]=par(p[x]); }
//p[par(a)] = par(b)
bool check(ll L){
ll bb=nb;
ll ma=0;
rep(i, na){
if(L<=d[i].f){
break;
}
while(dd[bb].f>L-m[d[i].f]){ // dd is the level
assert(bb>=0);
bb--;
}
//cout<<i<<' '<<dd[bb].f<<' '<<mm[dd[bb].f]<<' '<<d[i].f<<' '<<m[d[i].f]<<endl;
ma=max(mm[dd[bb].f]+m[d[i].f], ma);
}
//cout<<L<<' '<<ma<<endl;
return ma<k;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>na>>nb>>k;
rep(i,n) p[i] = i;
rep(i,n) ngs[i]=1;
rep(i,na){
cin>>d[i].s.f>>d[i].s.s>>d[i].f;
}
sort(d+1, d+na+1);
rep(i,na){
//cout<<d[i].f<<' ';
if(par(d[i].s.s)==par(d[i].s.f)){
m[d[i].f]=m[d[i-1].f];
continue;
}
ll init=ngs[par(d[i].s.s)]*(ngs[par(d[i].s.s)]-1)/2+ngs[par(d[i].s.f)]*(ngs[par(d[i].s.f)]-1)/2;
ll nogrps= ngs[par(d[i].s.s)]+ngs[par(d[i].s.f)];
p[par(d[i].s.s)] = par(d[i].s.f);
ngs[par(d[i].s.s)] = nogrps;
sum+=nogrps*(nogrps-1)/2-init;
m[d[i].f]=sum;
//cout<<sum<<endl;
}
rep(i,nb){
cin>>dd[i].s.f>>dd[i].s.s>>dd[i].f;
}
rep(i,n) p[i] = i;
rep(i,n) ngs[i]=1;
sort(dd+1, dd+nb+1);
sum=0;
rep(i,nb){
//cout<<dd[i].f<<' ';
if(par(dd[i].s.s)==par(dd[i].s.f)){
mm[dd[i].f]=mm[dd[i-1].f];
continue;
}
ll init=ngs[par(dd[i].s.s)]*(ngs[par(dd[i].s.s)]-1)/2+ngs[par(dd[i].s.f)]*(ngs[par(dd[i].s.f)]-1)/2;
ll nogrps= ngs[par(dd[i].s.s)]+ngs[par(dd[i].s.f)];
p[par(dd[i].s.s)] = par(dd[i].s.f);
ngs[par(dd[i].s.s)] = nogrps;
sum+=nogrps*(nogrps-1)/2-init;
mm[dd[i].f]=sum;
//cout<<sum<<endl;
}
ll maxn=d[na].f+dd[nb].f;
ll s=-1, e=maxn, mid;
while(mid=(e+s)/2, e-s>1){
if(check(mid)) s=mid;
else e=mid;
}
cout<<e;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
9736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
181 ms |
60836 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9684 KB |
Output is correct |
2 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
9736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |