oj.uz

Submission #546124

# Submission time Handle Problem Language Result Execution time Memory
546124 2022-04-06T12:30:23 Z leaked Reconstruction Project (JOI22_reconstruction) C++14
42 / 100
 5000 ms 418824 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(int j=0;j<sz(cur);j++){
                if(mg(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++) make(j);
            cur.insert(cur.begin(),i);
            for(int j=0;j<sz(cur);j++){
                if(mg(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;
//    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:128:13: warning: unused variable 'lw' [-Wunused-variable]
  128 |         int lw=0;
      |             ^~
reconstruction.cpp:130:13: warning: unused variable '_sam' [-Wunused-variable]
  130 |         int _sam=0;
      |             ^~~~
reconstruction.cpp:157:13: warning: unused variable 'xt' [-Wunused-variable]
  157 |         int xt=x[i];
      |             ^~
reconstruction.cpp:159:12: warning: unused variable 'anst' [-Wunused-variable]
  159 |         ll anst=1e18;
      |            ^~~~
reconstruction.cpp:106:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  106 |     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 0 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 1 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 0 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 1 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 2139 ms 409316 KB Output is correct
21 Correct 1448 ms 409196 KB Output is correct
22 Correct 1481 ms 409156 KB Output is correct
23 Correct 1560 ms 409068 KB Output is correct
24 Correct 1787 ms 409188 KB Output is correct
25 Correct 2017 ms 409384 KB Output is correct
26 Correct 2075 ms 409388 KB Output is correct
27 Correct 2053 ms 409532 KB Output is correct
28 Correct 2055 ms 409376 KB Output is correct
29 Correct 1313 ms 406376 KB Output is correct
30 Correct 2016 ms 409460 KB Output is correct
31 Correct 2017 ms 409440 KB Output is correct
32 Correct 2020 ms 409392 KB Output is correct
33 Correct 2032 ms 409616 KB Output is correct
34 Correct 1289 ms 379452 KB Output is correct
35 Correct 2036 ms 409484 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 5096 ms 418824 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 0 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 1 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 5075 ms 13920 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 0 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 1 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 2139 ms 409316 KB Output is correct
21 Correct 1448 ms 409196 KB Output is correct
22 Correct 1481 ms 409156 KB Output is correct
23 Correct 1560 ms 409068 KB Output is correct
24 Correct 1787 ms 409188 KB Output is correct
25 Correct 2017 ms 409384 KB Output is correct
26 Correct 2075 ms 409388 KB Output is correct
27 Correct 2053 ms 409532 KB Output is correct
28 Correct 2055 ms 409376 KB Output is correct
29 Correct 1313 ms 406376 KB Output is correct
30 Correct 2016 ms 409460 KB Output is correct
31 Correct 2017 ms 409440 KB Output is correct
32 Correct 2020 ms 409392 KB Output is correct
33 Correct 2032 ms 409616 KB Output is correct
34 Correct 1289 ms 379452 KB Output is correct
35 Correct 2036 ms 409484 KB Output is correct
36 Correct 2888 ms 410096 KB Output is correct
37 Correct 2203 ms 410036 KB Output is correct
38 Correct 2260 ms 409972 KB Output is correct
39 Correct 2400 ms 410100 KB Output is correct
40 Correct 2594 ms 410144 KB Output is correct
41 Correct 2795 ms 410084 KB Output is correct
42 Correct 2902 ms 410100 KB Output is correct
43 Correct 2899 ms 410140 KB Output is correct
44 Correct 2862 ms 410160 KB Output is correct
45 Correct 1804 ms 407320 KB Output is correct
46 Correct 2874 ms 410112 KB Output is correct
47 Correct 2873 ms 410400 KB Output is correct
48 Correct 2871 ms 410096 KB Output is correct
49 Correct 2899 ms 410096 KB Output is correct
50 Correct 1591 ms 380372 KB Output is correct
51 Correct 2722 ms 410452 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 0 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 1 ms 212 KB Output is correct
9 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 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 2139 ms 409316 KB Output is correct
21 Correct 1448 ms 409196 KB Output is correct
22 Correct 1481 ms 409156 KB Output is correct
23 Correct 1560 ms 409068 KB Output is correct
24 Correct 1787 ms 409188 KB Output is correct
25 Correct 2017 ms 409384 KB Output is correct
26 Correct 2075 ms 409388 KB Output is correct
27 Correct 2053 ms 409532 KB Output is correct
28 Correct 2055 ms 409376 KB Output is correct
29 Correct 1313 ms 406376 KB Output is correct
30 Correct 2016 ms 409460 KB Output is correct
31 Correct 2017 ms 409440 KB Output is correct
32 Correct 2020 ms 409392 KB Output is correct
33 Correct 2032 ms 409616 KB Output is correct
34 Correct 1289 ms 379452 KB Output is correct
35 Correct 2036 ms 409484 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 5096 ms 418824 KB Time limit exceeded
40 Halted 0 ms 0 KB -