oj.uz

Submission #546122

# Submission time Handle Problem Language Result Execution time Memory
546122 2022-04-06T12:07:26 Z leaked Reconstruction Project (JOI22_reconstruction) C++14
42 / 100
 5000 ms 423088 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=501;
int p[N],sz[N];
void make(int v){
    p[v]=v;sz[v]=1;
}
int get(int v){
    return p[v]=(p[v]==v?v:get(p[v]));
}
bool mg(int a,int b){
    a=get(a),b=get(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;
    vec<array<int,3>> arr;
    for(int i=0;i<m;i++){
        int v,u,w;
        cin>>v>>u>>w;--v;--u;
        arr.pb({w,v,u});
    }
    arr.pb({(int)-1e9-10,0,0});
    sort(all(arr));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++) make(j);
            cur.insert(cur.begin(),i);
            for(auto &z : cur){
                if(mg(arr[z][1],arr[z][2]))
                    rgt[i].pb(z);
            }
            cur=rgt[i];
        }
    }
    {
        vec<int> cur;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++) make(j);
            cur.insert(cur.begin(),i);
            for(auto &z : cur){
                if(mg(arr[z][1],arr[z][2]))
                    lft[i].pb(z);
            }
            cur=lft[i];
        }
    }
    vec<int> kek;
//    for(int i=0;i<m;i++){
//        for(auto &z : lft[i])
//            cout<<z[0]<<' '<<z[1]<<' '<<z[2]<<endl;
//    }
//    for(auto &z : arr) kek.pb(z[0]);
//    for(int i=1;i<m;i++)
//        kek.pb((arr[i][0]+arr[i][1])/2);
//    sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    int j;
    vec<int> lower;
    vec<int> same;
    vec<ll> ans;
    arr.pb({(int)1e9+1,-1,-1});
    int q;
    cin>>q;

    vec<int> x(q);
    for(auto &z : x) cin>>z;
    kek=x;
    vec<array<int,3>> my;
    auto stupid=[&](int x){
        my=arr;
        for(auto &z : my) z[0]=abs(x-z[0]);
        sort(all(my));
        for(int i=0;i<n;i++) make(i);
        ll ans=0;
        for(auto &z : my){
            if(mg(z[1],z[2]))
                ans+=z[0];
        }
        return ans;
    };
    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;
    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]) && get(arr[lft[j][f]][1])==get(arr[lft[j][f]][2])) ++f;
            while(s!=sz(rgt[j+1]) && get(arr[rgt[j+1][s]][1])==get(arr[rgt[j+1][s]][2])) ++s;
//            cout<<"HEY "<<f<<' '<<s<<' '<<sz(lft[j])<<' '<<sz(rgt[j+1])<<endl;
            if(s!=sz(rgt[j+1]) && (f==sz(lft[j]) || (z-arr[lft[j][f]][0])>(arr[rgt[j+1][s]][0]-z))){
                assert(mg(arr[rgt[j+1][s]][1],arr[rgt[j+1][s]][2]));
//                assert(rgt[j+1][s][0]>=z);

                cur+=arr[rgt[j+1][s]][0]-z;
                ++s;
            }
            else{
                assert(mg(arr[lft[j][f]][1],arr[lft[j][f]][2]));

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

                ++f;
            }
        }
//        cout<<"WOW "<<z<<' '<<cur<<' '<<lw<<endl;
        ans.pb(cur);
    }
//    int q;
//    cin>>q;
    for(int i=0;i<q;i++){
        int xt=x[i];
//        cin>>x;
        ll anst=1e18;
        int j=i;
//        int j=upper_bound(all(kek),xt)-kek.begin();
////        if(j!=sz(kek)){
//////            umin(anst,ans[j]-1ll*lower[j]*(kek[j]-xt)+1ll*(n-1-lower[j])*(kek[j]-xt));
//////        }
//        --j;
////        assert(kek[j]==xt);
////        if(j>=0) umin(anst,ans[j]);
////        assert(anst>=stupid(xt));
        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
1
10
17
*/

Compilation message

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:118:13: warning: unused variable 'lw' [-Wunused-variable]
  118 |         int lw=0;
      |             ^~
reconstruction.cpp:120:13: warning: unused variable '_sam' [-Wunused-variable]
  120 |         int _sam=0;
      |             ^~~~
reconstruction.cpp:147:13: warning: unused variable 'xt' [-Wunused-variable]
  147 |         int xt=x[i];
      |             ^~
reconstruction.cpp:149:12: warning: unused variable 'anst' [-Wunused-variable]
  149 |         ll anst=1e18;
      |            ^~~~
reconstruction.cpp:96:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
   96 |     auto stupid=[&](int x){
      |          ^~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2428 ms 409436 KB Output is correct
21 Correct 2208 ms 409256 KB Output is correct
22 Correct 2277 ms 409332 KB Output is correct
23 Correct 2288 ms 409140 KB Output is correct
24 Correct 2339 ms 409376 KB Output is correct
25 Correct 2411 ms 409480 KB Output is correct
26 Correct 2434 ms 409520 KB Output is correct
27 Correct 2418 ms 409384 KB Output is correct
28 Correct 2393 ms 409664 KB Output is correct
29 Correct 2157 ms 406532 KB Output is correct
30 Correct 2428 ms 409572 KB Output is correct
31 Correct 2427 ms 409608 KB Output is correct
32 Correct 2431 ms 409512 KB Output is correct
33 Correct 2402 ms 409604 KB Output is correct
34 Correct 1749 ms 379572 KB Output is correct
35 Correct 2414 ms 409444 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 5099 ms 423088 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2428 ms 409436 KB Output is correct
21 Correct 2208 ms 409256 KB Output is correct
22 Correct 2277 ms 409332 KB Output is correct
23 Correct 2288 ms 409140 KB Output is correct
24 Correct 2339 ms 409376 KB Output is correct
25 Correct 2411 ms 409480 KB Output is correct
26 Correct 2434 ms 409520 KB Output is correct
27 Correct 2418 ms 409384 KB Output is correct
28 Correct 2393 ms 409664 KB Output is correct
29 Correct 2157 ms 406532 KB Output is correct
30 Correct 2428 ms 409572 KB Output is correct
31 Correct 2427 ms 409608 KB Output is correct
32 Correct 2431 ms 409512 KB Output is correct
33 Correct 2402 ms 409604 KB Output is correct
34 Correct 1749 ms 379572 KB Output is correct
35 Correct 2414 ms 409444 KB Output is correct
36 Correct 3238 ms 410284 KB Output is correct
37 Correct 2994 ms 410124 KB Output is correct
38 Correct 3129 ms 410016 KB Output is correct
39 Correct 3161 ms 410044 KB Output is correct
40 Correct 3191 ms 410096 KB Output is correct
41 Correct 3257 ms 410288 KB Output is correct
42 Correct 3236 ms 410176 KB Output is correct
43 Correct 3240 ms 410436 KB Output is correct
44 Correct 3246 ms 410304 KB Output is correct
45 Correct 2612 ms 407168 KB Output is correct
46 Correct 3253 ms 410120 KB Output is correct
47 Correct 3279 ms 410092 KB Output is correct
48 Correct 3248 ms 410220 KB Output is correct
49 Correct 3271 ms 410376 KB Output is correct
50 Correct 2039 ms 380336 KB Output is correct
51 Correct 3133 ms 410264 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 2428 ms 409436 KB Output is correct
21 Correct 2208 ms 409256 KB Output is correct
22 Correct 2277 ms 409332 KB Output is correct
23 Correct 2288 ms 409140 KB Output is correct
24 Correct 2339 ms 409376 KB Output is correct
25 Correct 2411 ms 409480 KB Output is correct
26 Correct 2434 ms 409520 KB Output is correct
27 Correct 2418 ms 409384 KB Output is correct
28 Correct 2393 ms 409664 KB Output is correct
29 Correct 2157 ms 406532 KB Output is correct
30 Correct 2428 ms 409572 KB Output is correct
31 Correct 2427 ms 409608 KB Output is correct
32 Correct 2431 ms 409512 KB Output is correct
33 Correct 2402 ms 409604 KB Output is correct
34 Correct 1749 ms 379572 KB Output is correct
35 Correct 2414 ms 409444 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Execution timed out 5099 ms 423088 KB Time limit exceeded
40 Halted 0 ms 0 KB -