oj.uz

Submission #694017

# Submission time Handle Problem Language Result Execution time Memory
694017 2023-02-03T14:44:15 Z safaricola Phone Plans (CCO22_day2problem2) C++17
5 / 25
 1616 ms 56184 KB 
#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;
    while(dd[bb].f>L)bb--;
    ma=mm[dd[bb].f];
    rep(i, na){
        if(L<d[i].f){
            break;
        }
        while(dd[bb].f>L-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){
        if(par(dd[i].s.s)==par(dd[i].s.f)){
            mm[dd[i].f]=mm[dd[i-1].f]; 
            continue;
        }
        //cout<<dd[nb].f<<endl;
        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;
    }
    //cout<<d[na].f<<' '<<dd[nb].f<<endl;
    ll maxn=d[na].f+dd[nb].f;
    ll s=-1, e=maxn+1, mid;
    while(mid=(e+s)/2, e-s>1){
        if(check(mid)) s=mid;
        else e=mid;
    }
    if(e==maxn+1)cout<<-1;
    else cout<<e;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 30668 KB Output is correct
2 Correct 176 ms 30668 KB Output is correct
3 Correct 151 ms 30664 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 9684 KB Output is correct
6 Correct 5 ms 9628 KB Output is correct
7 Correct 1608 ms 45176 KB Output is correct
8 Correct 162 ms 20004 KB Output is correct
9 Correct 157 ms 31008 KB Output is correct
10 Correct 299 ms 31048 KB Output is correct
11 Correct 1591 ms 48288 KB Output is correct
12 Correct 1584 ms 48704 KB Output is correct
13 Correct 1571 ms 49048 KB Output is correct
14 Correct 1589 ms 49064 KB Output is correct
15 Correct 8 ms 12884 KB Output is correct
16 Correct 7 ms 12856 KB Output is correct
17 Correct 6 ms 12756 KB Output is correct
18 Correct 374 ms 56180 KB Output is correct
19 Correct 374 ms 48456 KB Output is correct
20 Correct 383 ms 48216 KB Output is correct
21 Correct 387 ms 48312 KB Output is correct
22 Correct 384 ms 48380 KB Output is correct
23 Correct 451 ms 48292 KB Output is correct
24 Correct 590 ms 48288 KB Output is correct
25 Correct 660 ms 48324 KB Output is correct
26 Correct 775 ms 48328 KB Output is correct
27 Correct 1616 ms 48288 KB Output is correct
28 Correct 389 ms 56184 KB Output is correct
29 Correct 393 ms 48284 KB Output is correct
30 Correct 369 ms 48292 KB Output is correct
31 Correct 382 ms 48332 KB Output is correct
32 Correct 366 ms 48136 KB Output is correct
33 Correct 394 ms 47136 KB Output is correct
34 Correct 541 ms 35780 KB Output is correct
35 Correct 546 ms 35680 KB Output is correct
36 Correct 556 ms 35808 KB Output is correct
37 Correct 1359 ms 35780 KB Output is correct
38 Correct 752 ms 34248 KB Output is correct
39 Correct 577 ms 34208 KB Output is correct
40 Correct 535 ms 34200 KB Output is correct
41 Correct 534 ms 34212 KB Output is correct
42 Correct 344 ms 45112 KB Output is correct
43 Correct 1532 ms 45244 KB Output is correct
44 Correct 356 ms 45168 KB Output is correct
45 Correct 359 ms 45260 KB Output is correct
46 Correct 466 ms 48252 KB Output is correct
47 Correct 645 ms 48288 KB Output is correct
48 Correct 1581 ms 48288 KB Output is correct
49 Correct 178 ms 23256 KB Output is correct
50 Correct 185 ms 23256 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 135 ms 27960 KB Output is correct
4 Correct 62 ms 15436 KB Output is correct
5 Correct 146 ms 31072 KB Output is correct
6 Correct 141 ms 31068 KB Output is correct
7 Correct 153 ms 31072 KB Output is correct
8 Correct 7 ms 12756 KB Output is correct
9 Correct 116 ms 31076 KB Output is correct
10 Correct 118 ms 32588 KB Output is correct
11 Correct 131 ms 30980 KB Output is correct
12 Correct 124 ms 33336 KB Output is correct
13 Correct 7 ms 12756 KB Output is correct
14 Correct 7 ms 12748 KB Output is correct
15 Correct 7 ms 12756 KB Output is correct
16 Correct 166 ms 34448 KB Output is correct
17 Correct 159 ms 31036 KB Output is correct
18 Correct 141 ms 30956 KB Output is correct
19 Correct 138 ms 31052 KB Output is correct
20 Correct 145 ms 31008 KB Output is correct
21 Correct 145 ms 31080 KB Output is correct
22 Correct 142 ms 31024 KB Output is correct
23 Correct 139 ms 31052 KB Output is correct
24 Correct 146 ms 31052 KB Output is correct
25 Correct 140 ms 31052 KB Output is correct
26 Correct 149 ms 34508 KB Output is correct
27 Correct 151 ms 30996 KB Output is correct
28 Correct 143 ms 31052 KB Output is correct
29 Incorrect 163 ms 31060 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -