oj.uz

Submission #546138

# Submission time Handle Problem Language Result Execution time Memory
546138 2022-04-06T13:41:33 Z leaked Reconstruction Project (JOI22_reconstruction) C++14
35 / 100
 5000 ms 41712 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_prep ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e6+1;
const int inf=1e9+1;
int p[N],sz[N];
vec<array<int,3>> torall;
void make(int v){
    p[v]=v;sz[v]=1;
}
int get(int v){
    return (p[v]==v?v:get(p[v]));
}
int tmr;
bool mg(int a,int b){
    a=get(a),b=get(b);
    if(a==b) return 0;

    torall.pb({tmr,a,sz[a]});
    torall.pb({tmr,b,sz[b]});

    if(sz[a]<sz[b]) swap(a,b);
    p[b]=a;sz[a]+=sz[b];
    return 1;
}


vec<int> kek;
struct fenwick{
    ll fnw[N];
    fenwick(){
        fill(fnw,fnw+N,0);
    }
    void upd(int i,int x){
        i=upper_bound(all(kek),i)-kek.begin()-1;
        ++i;
        while(i<=sz(kek)){
            fnw[i]+=x;
            i+=i&-i;
        }
    }
    ll get(int i){
        i=upper_bound(all(kek),i)-kek.begin()-1;
        ++i;
        ll ans=0;
        while(i>0){
            ans+=fnw[i];
            i-=i&-i;
        }
        return ans;
    }
    ll get(int l,int r){
        return get(r)-get(l-1);
    }
}fi,si;

ll ans[N];
array<int,3> arr[N];
int x[N];
int cnt[N];
void rec(const vec<int> &cur,int v,int tl,int tr){
    vec<int> ncur;
    tmr=v;
    for(auto &z : cur) cnt[z]=0;
    auto f=[&](int x){
        ncur=cur;
//        if(tl==0 && tr==1)
//            assert(!sz(torall));
//        cerr<<"DEBUG "<<sz(ncur)<<' '<<x<<endl;
        sort(all(ncur),[&](int i,int j){return abs(arr[i][0]-x)<abs(arr[j][0]-x);});
//        for(auto &z : ncur) make(arr[z][1]),make(arr[z][2]);
        for(auto &z : ncur){
//            cout<<"KEY "<<abs(arr[z][0]-x)<<endl;
            if(mg(arr[z][1],arr[z][2])){
                ++cnt[z];
            }
        }
        while(sz(torall) && torall.back()[0]==v){
            int u=torall.back()[1];sz[u]=torall.back()[2];p[u]=u;
            torall.pop_back();
        }
    };
//    for(auto &z : cur)
////        cout<<"HEY "<<z<<endl;
//    cout<<endl;
    f(x[tl]);f(x[tr]);

    vec<int> del;
    ncur.clear();
    for(auto &z : cur){
        if(cnt[z]==2){
            del.pb(z);
            mg(arr[z][1],arr[z][2]);
//            cout<<"DEL "<<arr[z][0]<<' '<<tl<<' '<<tr<<' '<<arr[z][1]<<' '<<arr[z][2]<<endl;
        }
//        else ncur.pb(z);
    }
    for(auto &z : cur){
        if(get(arr[z][1])!=get(arr[z][2])){
            ncur.pb(z);
//            mg(arr[z][1],arr[z][2]);
//            cout<<"DEL "<<arr[z][0]<<' '<<tl<<' '<<tr<<' '<<arr[z][1]<<' '<<arr[z][2]<<endl;
        }
//        else ncur.pb(z);
    }
//    cout<<endl;
    ///szhat'
    for(auto &z : del) fi.upd(arr[z][0],1),si.upd(arr[z][0],arr[z][0]);
    if(tl==tr){
        ans[tl]=si.get(x[tl],inf)-1ll*fi.get(x[tl],inf)*x[tl]
            -si.get(0,x[tl]-1)+1ll*fi.get(0,x[tl]-1)*x[tl];
    }
    else{
        int tm=(tl+tr)>>1;
        rec(ncur,2*v,tl,tm);
        rec(ncur,2*v+1,tm+1,tr);
    }
    for(auto &z : del) fi.upd(arr[z][0],-1),si.upd(arr[z][0],-arr[z][0]);
    while(sz(torall) && torall.back()[0]==v){
        int u=torall.back()[1];sz[u]=torall.back()[2];p[u]=u;
        torall.pop_back();
    }
}
signed main(){
    fast_prep;
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int v,u,w;
        cin>>v>>u>>w;--v;--u;
        arr[i]={w,v,u};
        kek.pb(w);
    }
    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    int q;cin>>q;
    for(int i=0;i<q;i++) cin>>x[i];
    for(int i=0;i<n;i++) make(i);
    vec<int> p(m);iota(all(p),0);
    rec(p,1,0,q-1);
    for(int i=0;i<q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}
/*
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
3
3
6
13
17

5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
1
10
17
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 6 ms 15984 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15944 KB Output is correct
9 Correct 7 ms 15920 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15904 KB Output is correct
14 Correct 6 ms 15956 KB Output is correct
15 Correct 6 ms 15940 KB Output is correct
16 Correct 6 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 6 ms 15984 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15944 KB Output is correct
9 Correct 7 ms 15920 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15904 KB Output is correct
14 Correct 6 ms 15956 KB Output is correct
15 Correct 6 ms 15940 KB Output is correct
16 Correct 6 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 6 ms 15956 KB Output is correct
20 Correct 594 ms 20556 KB Output is correct
21 Correct 606 ms 20496 KB Output is correct
22 Correct 604 ms 20468 KB Output is correct
23 Correct 603 ms 20428 KB Output is correct
24 Correct 613 ms 20576 KB Output is correct
25 Correct 610 ms 20428 KB Output is correct
26 Correct 592 ms 20428 KB Output is correct
27 Correct 605 ms 20592 KB Output is correct
28 Correct 475 ms 20440 KB Output is correct
29 Correct 247 ms 20272 KB Output is correct
30 Correct 601 ms 20428 KB Output is correct
31 Correct 616 ms 20424 KB Output is correct
32 Correct 597 ms 20428 KB Output is correct
33 Correct 608 ms 20572 KB Output is correct
34 Correct 45 ms 18852 KB Output is correct
35 Correct 63 ms 18868 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15960 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Execution timed out 5062 ms 27140 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 6 ms 15984 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15944 KB Output is correct
9 Correct 7 ms 15920 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15904 KB Output is correct
14 Correct 6 ms 15956 KB Output is correct
15 Correct 6 ms 15940 KB Output is correct
16 Correct 6 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 6 ms 15956 KB Output is correct
20 Correct 401 ms 40232 KB Output is correct
21 Correct 368 ms 40172 KB Output is correct
22 Correct 363 ms 40220 KB Output is correct
23 Correct 383 ms 40228 KB Output is correct
24 Correct 404 ms 40300 KB Output is correct
25 Correct 385 ms 40244 KB Output is correct
26 Correct 374 ms 40268 KB Output is correct
27 Correct 288 ms 40140 KB Output is correct
28 Correct 451 ms 40236 KB Output is correct
29 Correct 377 ms 40256 KB Output is correct
30 Correct 364 ms 41712 KB Output is correct
31 Correct 358 ms 40280 KB Output is correct
32 Correct 240 ms 40516 KB Output is correct
33 Correct 324 ms 39752 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 6 ms 15984 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15944 KB Output is correct
9 Correct 7 ms 15920 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15904 KB Output is correct
14 Correct 6 ms 15956 KB Output is correct
15 Correct 6 ms 15940 KB Output is correct
16 Correct 6 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 6 ms 15956 KB Output is correct
20 Correct 594 ms 20556 KB Output is correct
21 Correct 606 ms 20496 KB Output is correct
22 Correct 604 ms 20468 KB Output is correct
23 Correct 603 ms 20428 KB Output is correct
24 Correct 613 ms 20576 KB Output is correct
25 Correct 610 ms 20428 KB Output is correct
26 Correct 592 ms 20428 KB Output is correct
27 Correct 605 ms 20592 KB Output is correct
28 Correct 475 ms 20440 KB Output is correct
29 Correct 247 ms 20272 KB Output is correct
30 Correct 601 ms 20428 KB Output is correct
31 Correct 616 ms 20424 KB Output is correct
32 Correct 597 ms 20428 KB Output is correct
33 Correct 608 ms 20572 KB Output is correct
34 Correct 45 ms 18852 KB Output is correct
35 Correct 63 ms 18868 KB Output is correct
36 Execution timed out 5065 ms 24524 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 6 ms 15984 KB Output is correct
7 Correct 7 ms 15956 KB Output is correct
8 Correct 7 ms 15944 KB Output is correct
9 Correct 7 ms 15920 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15904 KB Output is correct
14 Correct 6 ms 15956 KB Output is correct
15 Correct 6 ms 15940 KB Output is correct
16 Correct 6 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 6 ms 15956 KB Output is correct
20 Correct 594 ms 20556 KB Output is correct
21 Correct 606 ms 20496 KB Output is correct
22 Correct 604 ms 20468 KB Output is correct
23 Correct 603 ms 20428 KB Output is correct
24 Correct 613 ms 20576 KB Output is correct
25 Correct 610 ms 20428 KB Output is correct
26 Correct 592 ms 20428 KB Output is correct
27 Correct 605 ms 20592 KB Output is correct
28 Correct 475 ms 20440 KB Output is correct
29 Correct 247 ms 20272 KB Output is correct
30 Correct 601 ms 20428 KB Output is correct
31 Correct 616 ms 20424 KB Output is correct
32 Correct 597 ms 20428 KB Output is correct
33 Correct 608 ms 20572 KB Output is correct
34 Correct 45 ms 18852 KB Output is correct
35 Correct 63 ms 18868 KB Output is correct
36 Correct 9 ms 15960 KB Output is correct
37 Correct 6 ms 15956 KB Output is correct
38 Correct 6 ms 15956 KB Output is correct
39 Execution timed out 5062 ms 27140 KB Time limit exceeded
40 Halted 0 ms 0 KB -