oj.uz

Submission #546137

# Submission time Handle Problem Language Result Execution time Memory
546137 2022-04-06T13:38:20 Z leaked Reconstruction Project (JOI22_reconstruction) C++14
7 / 100
 5000 ms 30832 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);
    }
//    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 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15916 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 9 ms 16084 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 7 ms 15956 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15916 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 9 ms 16084 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 7 ms 15956 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 614 ms 20456 KB Output is correct
21 Correct 633 ms 20424 KB Output is correct
22 Correct 629 ms 20484 KB Output is correct
23 Correct 591 ms 20496 KB Output is correct
24 Correct 590 ms 20440 KB Output is correct
25 Correct 614 ms 20452 KB Output is correct
26 Correct 604 ms 20452 KB Output is correct
27 Correct 612 ms 20472 KB Output is correct
28 Correct 485 ms 20536 KB Output is correct
29 Correct 316 ms 20432 KB Output is correct
30 Correct 599 ms 20396 KB Output is correct
31 Correct 617 ms 20548 KB Output is correct
32 Correct 606 ms 20452 KB Output is correct
33 Correct 618 ms 20464 KB Output is correct
34 Correct 296 ms 20376 KB Output is correct
35 Correct 592 ms 20432 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 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Execution timed out 5051 ms 30832 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15916 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 9 ms 16084 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 7 ms 15956 KB Output is correct
19 Correct 6 ms 15956 KB Output is correct
20 Execution timed out 5083 ms 20308 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15916 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 9 ms 16084 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 7 ms 15956 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 614 ms 20456 KB Output is correct
21 Correct 633 ms 20424 KB Output is correct
22 Correct 629 ms 20484 KB Output is correct
23 Correct 591 ms 20496 KB Output is correct
24 Correct 590 ms 20440 KB Output is correct
25 Correct 614 ms 20452 KB Output is correct
26 Correct 604 ms 20452 KB Output is correct
27 Correct 612 ms 20472 KB Output is correct
28 Correct 485 ms 20536 KB Output is correct
29 Correct 316 ms 20432 KB Output is correct
30 Correct 599 ms 20396 KB Output is correct
31 Correct 617 ms 20548 KB Output is correct
32 Correct 606 ms 20452 KB Output is correct
33 Correct 618 ms 20464 KB Output is correct
34 Correct 296 ms 20376 KB Output is correct
35 Correct 592 ms 20432 KB Output is correct
36 Execution timed out 5055 ms 25248 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15916 KB Output is correct
11 Correct 7 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 9 ms 16084 KB Output is correct
14 Correct 7 ms 16016 KB Output is correct
15 Correct 7 ms 15956 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 6 ms 15956 KB Output is correct
18 Correct 7 ms 15956 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 614 ms 20456 KB Output is correct
21 Correct 633 ms 20424 KB Output is correct
22 Correct 629 ms 20484 KB Output is correct
23 Correct 591 ms 20496 KB Output is correct
24 Correct 590 ms 20440 KB Output is correct
25 Correct 614 ms 20452 KB Output is correct
26 Correct 604 ms 20452 KB Output is correct
27 Correct 612 ms 20472 KB Output is correct
28 Correct 485 ms 20536 KB Output is correct
29 Correct 316 ms 20432 KB Output is correct
30 Correct 599 ms 20396 KB Output is correct
31 Correct 617 ms 20548 KB Output is correct
32 Correct 606 ms 20452 KB Output is correct
33 Correct 618 ms 20464 KB Output is correct
34 Correct 296 ms 20376 KB Output is correct
35 Correct 592 ms 20432 KB Output is correct
36 Correct 7 ms 15956 KB Output is correct
37 Correct 8 ms 15956 KB Output is correct
38 Correct 7 ms 15956 KB Output is correct
39 Execution timed out 5051 ms 30832 KB Time limit exceeded
40 Halted 0 ms 0 KB -