제출 #546113

#제출 시각아이디문제언어결과실행 시간메모리
546113leakedReconstruction Project (JOI22_reconstruction)C++14
0 / 100
1 ms212 KiB
#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); #define int long long 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}); } sort(all(arr)); vec<vec<array<int,3>>> lft(m+1); auto rgt=lft; /// let's try { vec<array<int,3>> cur; for(int i=m-1;i>=0;i--){ for(int j=0;j<n;j++) make(j); cur.insert(cur.begin(),arr[i]); for(auto &z : cur){ if(mg(z[1],z[2])) rgt[i].pb(z); } cur=rgt[i]; } } { vec<array<int,3>> cur; for(int i=0;i<m;i++){ for(int j=0;j<n;j++) make(j); cur.insert(cur.begin(),arr[i]); for(auto &z : cur){ if(mg(z[1],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=0; vec<int> lower; vec<int> same; vec<ll> ans; arr.pb({(int)1e9,-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(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; while(rem--){ while(f!=sz(lft[j]) && get(lft[j][f][1])==get(lft[j][f][2])) ++f; while(s!=sz(rgt[j+1]) && get(rgt[j+1][s][1])==get(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-lft[j][f][0])>(rgt[j+1][s][0]-z))){ assert(mg(rgt[j+1][s][1],rgt[j+1][s][2])); cur+=rgt[j+1][s][0]-z; ++s; } else{ // return 0; assert(f!=sz(lft[j])); // cout<<"H assert(mg(lft[j][f][1],lft[j][f][2])); cur+=z-lft[j][f][0]; lw+=(z>lft[j][f][0]); _sam+=(z==lft[j][f][0]); ++f; } } // cout<<"WOW "<<z<<' '<<cur<<' '<<lw<<endl; lower.pb(lw); same.pb(_sam); 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=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 */

컴파일 시 표준 에러 (stderr) 메시지

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:150:12: warning: unused variable 'anst' [-Wunused-variable]
  150 |         ll anst=1e18;
      |            ^~~~
reconstruction.cpp:96:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
   96 |     auto stupid=[&](int x){
      |          ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...