oj.uz

Submission #546139

# Submission time Handle Problem Language Result Execution time Memory
546139 2022-04-06T13:47:06 Z leaked Reconstruction Project (JOI22_reconstruction) C++14
42 / 100
 5000 ms 433996 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();
    }
}

void make1(int v){
    p[v]=v;sz[v]=1;
}
int get1(int v){
    return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg1(int a,int b){
    a=get1(a),b=get1(b);
    if(a==b) return 0;
    if(sz[a]<sz[b]) swap(a,b);
    p[b]=a;sz[a]+=sz[b];
    return 1;
}

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];
    if(q<=1000){
        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;
    }

    arr[m]={(int)-inf-10,0,0};
    sort(arr,arr+m+1);m++;
    vec<vec<int>> lft(m+1);

    auto rgt=lft;
    /// let's try
    {
        vec<int> cur;
        for(int i=m-1;i>=0;i--){
            for(int j=0;j<n;j++) make1(j);
            cur.insert(cur.begin(),i);
            for(int j=0;j<sz(cur);j++){
                if(mg1(arr[cur[j]][1],arr[cur[j]][2]))
                    rgt[i].pb(cur[j]);
                else{
                    for(int k=j+1;k<sz(cur);k++)
                        rgt[i].pb(cur[k]);
                    break;
                }
            }
            cur=rgt[i];
        }
    }
    {
        vec<int> cur;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) make1(j);
            cur.insert(cur.begin(),i);
            for(int j=0;j<sz(cur);j++){
                if(mg1(arr[cur[j]][1],arr[cur[j]][2]))
                    lft[i].pb(cur[j]);
                else{
                    for(int k=j+1;k<sz(cur);k++)
                        lft[i].pb(cur[k]);
                    break;
                }
            }
            cur=lft[i];
        }
    }
    vec<int> kek;
    int j;
    vec<int> lower;
    vec<int> same;
    for(int i=0;i<q;i++) kek.pb(x[i]);
//    kek=x;
    vec<array<int,3>> my;
    for(int i=1;i<q;i++) assert(kek[i]>kek[i-1]);
    for(int j=1;j<m;j++) assert(arr[j][0]>=arr[j-1][0]);
    j=-1;
    int u=0;
    for(auto &z : kek){
        while(j+1<m && arr[j+1][0]<=z) ++j;
//        cout<<"HEY "<<z<<' '<<arr[j][0]<<' '<<arr[j+1][0]<<' '<<z<<endl;
        ///j and j+1
        int f=0,s=0;
        for(int i=0;i<n;i++) make(i);
        int rem=n-1;
        int lw=0;
        ll cur=0;
        int _sam=0;
//        assert(arr[j+1][0]>z && arr[j][0]<=z);
        while(rem--){
            while(f!=sz(lft[j]) && get1(arr[lft[j][f]][1])==get1(arr[lft[j][f]][2])) ++f;
            while(s!=sz(rgt[j+1]) && get1(arr[rgt[j+1][s]][1])==get1(arr[rgt[j+1][s]][2])) ++s;
            if(s!=sz(rgt[j+1]) && (f==sz(lft[j]) || (z-arr[lft[j][f]][0])>(arr[rgt[j+1][s]][0]-z))){
                assert(mg1(arr[rgt[j+1][s]][1],arr[rgt[j+1][s]][2]));
                cur+=arr[rgt[j+1][s]][0]-z;
                ++s;
            }
            else{
                assert(mg1(arr[lft[j][f]][1],arr[lft[j][f]][2]));

                cur+=z-arr[lft[j][f]][0];

                ++f;
            }
        }
        ans[u++]=cur;
//        ans.pb(cur);
    }
    for(int i=0;i<q;i++){
        int xt=x[i];
        ll anst=1e18;
        int j=i;
        cout<<ans[j]<<'\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
*/

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:234:13: warning: unused variable 'lw' [-Wunused-variable]
  234 |         int lw=0;
      |             ^~
reconstruction.cpp:236:13: warning: unused variable '_sam' [-Wunused-variable]
  236 |         int _sam=0;
      |             ^~~~
reconstruction.cpp:258:13: warning: unused variable 'xt' [-Wunused-variable]
  258 |         int xt=x[i];
      |             ^~
reconstruction.cpp:259:12: warning: unused variable 'anst' [-Wunused-variable]
  259 |         ll anst=1e18;
      |            ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 7 ms 15960 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15972 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 7 ms 15984 KB Output is correct
12 Correct 7 ms 15920 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15968 KB Output is correct
15 Correct 8 ms 15908 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 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 6 ms 15956 KB Output is correct
3 Correct 7 ms 15960 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15972 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 7 ms 15984 KB Output is correct
12 Correct 7 ms 15920 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15968 KB Output is correct
15 Correct 8 ms 15908 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 7 ms 15952 KB Output is correct
20 Correct 619 ms 20360 KB Output is correct
21 Correct 648 ms 20424 KB Output is correct
22 Correct 640 ms 20432 KB Output is correct
23 Correct 673 ms 20432 KB Output is correct
24 Correct 640 ms 20456 KB Output is correct
25 Correct 620 ms 20500 KB Output is correct
26 Correct 595 ms 20396 KB Output is correct
27 Correct 615 ms 20556 KB Output is correct
28 Correct 572 ms 20372 KB Output is correct
29 Correct 265 ms 20272 KB Output is correct
30 Correct 672 ms 20380 KB Output is correct
31 Correct 703 ms 20460 KB Output is correct
32 Correct 738 ms 20436 KB Output is correct
33 Correct 690 ms 20456 KB Output is correct
34 Correct 53 ms 18864 KB Output is correct
35 Correct 77 ms 18864 KB Output is correct

Subtask #3
0 / 7.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 8 ms 15956 KB Output is correct
4 Execution timed out 5081 ms 433996 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 7 ms 15960 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15972 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 7 ms 15984 KB Output is correct
12 Correct 7 ms 15920 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15968 KB Output is correct
15 Correct 8 ms 15908 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 7 ms 15956 KB Output is correct
20 Execution timed out 5082 ms 29268 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 7 ms 15960 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15972 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 7 ms 15984 KB Output is correct
12 Correct 7 ms 15920 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15968 KB Output is correct
15 Correct 8 ms 15908 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 7 ms 15952 KB Output is correct
20 Correct 619 ms 20360 KB Output is correct
21 Correct 648 ms 20424 KB Output is correct
22 Correct 640 ms 20432 KB Output is correct
23 Correct 673 ms 20432 KB Output is correct
24 Correct 640 ms 20456 KB Output is correct
25 Correct 620 ms 20500 KB Output is correct
26 Correct 595 ms 20396 KB Output is correct
27 Correct 615 ms 20556 KB Output is correct
28 Correct 572 ms 20372 KB Output is correct
29 Correct 265 ms 20272 KB Output is correct
30 Correct 672 ms 20380 KB Output is correct
31 Correct 703 ms 20460 KB Output is correct
32 Correct 738 ms 20436 KB Output is correct
33 Correct 690 ms 20456 KB Output is correct
34 Correct 53 ms 18864 KB Output is correct
35 Correct 77 ms 18864 KB Output is correct
36 Correct 2808 ms 426100 KB Output is correct
37 Correct 2155 ms 426040 KB Output is correct
38 Correct 2208 ms 425960 KB Output is correct
39 Correct 2357 ms 425924 KB Output is correct
40 Correct 2572 ms 426040 KB Output is correct
41 Correct 2759 ms 426176 KB Output is correct
42 Correct 2766 ms 426160 KB Output is correct
43 Correct 2792 ms 426172 KB Output is correct
44 Correct 2646 ms 426232 KB Output is correct
45 Correct 1719 ms 423116 KB Output is correct
46 Correct 2802 ms 426204 KB Output is correct
47 Correct 2787 ms 426116 KB Output is correct
48 Correct 2820 ms 426112 KB Output is correct
49 Correct 2858 ms 426076 KB Output is correct
50 Correct 1681 ms 396240 KB Output is correct
51 Correct 2771 ms 426084 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 6 ms 15956 KB Output is correct
3 Correct 7 ms 15960 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15972 KB Output is correct
7 Correct 9 ms 15956 KB Output is correct
8 Correct 8 ms 15956 KB Output is correct
9 Correct 7 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 7 ms 15984 KB Output is correct
12 Correct 7 ms 15920 KB Output is correct
13 Correct 7 ms 15956 KB Output is correct
14 Correct 7 ms 15968 KB Output is correct
15 Correct 8 ms 15908 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 6 ms 15956 KB Output is correct
19 Correct 7 ms 15952 KB Output is correct
20 Correct 619 ms 20360 KB Output is correct
21 Correct 648 ms 20424 KB Output is correct
22 Correct 640 ms 20432 KB Output is correct
23 Correct 673 ms 20432 KB Output is correct
24 Correct 640 ms 20456 KB Output is correct
25 Correct 620 ms 20500 KB Output is correct
26 Correct 595 ms 20396 KB Output is correct
27 Correct 615 ms 20556 KB Output is correct
28 Correct 572 ms 20372 KB Output is correct
29 Correct 265 ms 20272 KB Output is correct
30 Correct 672 ms 20380 KB Output is correct
31 Correct 703 ms 20460 KB Output is correct
32 Correct 738 ms 20436 KB Output is correct
33 Correct 690 ms 20456 KB Output is correct
34 Correct 53 ms 18864 KB Output is correct
35 Correct 77 ms 18864 KB Output is correct
36 Correct 7 ms 15956 KB Output is correct
37 Correct 7 ms 15956 KB Output is correct
38 Correct 8 ms 15956 KB Output is correct
39 Execution timed out 5081 ms 433996 KB Time limit exceeded
40 Halted 0 ms 0 KB -