Submission #951629

#	Time	Username	Problem	Language	Result	Execution time	Memory
951629		Darren0724	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5110 ms	409896 KiB

reconstruction

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx","avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long 
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=505;
const int M=1000005;
const ll INF=1e9;
struct DSU{
    vector<int> pa,sz;
    DSU(int n){
        pa.resize(n);
        sz.resize(n,1);
        iota(all(pa),0);
    }
    int Find(int k){
        return (k==pa[k]?k:pa[k]=Find(pa[k]));
    }
    void onion(int a,int b){
        a=Find(a),b=Find(b);
        if(a==b)return;
        if(sz[a]>sz[b]){
            swap(a,b);
        }
        pa[a]=b;
        sz[b]+=sz[a];
    }
    int same(int a,int b){
        return Find(a)==Find(b);
    }
};  
vector<int> e(M);
set<int> adj[N];
int get_mn(int k,int pa,int goal){
    if(k==goal){
        return INF;
    }
    for(int j:adj[k]){
        int to=k^e[j];
        if(to==pa)continue;
        int tmp=get_mn(to,k,goal);
        if(tmp!=-1){
            return min(tmp,j);
        }
    }
    return -1;
}
int get_mx(int k,int pa,int goal){
    if(k==goal){
        return -INF;
    }
    for(int j:adj[k]){
        int to=k^e[j];
        if(to==pa)continue;
        int tmp=get_mx(to,k,goal);
        if(tmp!=-1){
            return max(tmp,j);
        }
    }
    return -1;
}
int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<array<int,3>> v(m);
    for(int i=0;i<m;i++){
        cin>>v[i][1]>>v[i][2]>>v[i][0];
    }
    sort(all(v));
    for(int i=0;i<m;i++){
        e[i]=v[i][1]^v[i][2];
    }
    vector<int> l[m],r[m];
    vector<int> t;
    for(int i=0;i<m;i++){
        int id=get_mn(v[i][1],v[i][1],v[i][2]);
        if(id!=-1){
            adj[v[id][1]].erase(id);
            adj[v[id][2]].erase(id);
            for(auto it=t.begin();it!=t.end();it++){
                if(*it==id){
                    t.erase(it);
                    break;
                }
            }
        }
        t.push_back(i);
        adj[v[i][1]].insert(i);
        adj[v[i][2]].insert(i);
        l[i]=t;
        sort(all(l[i]),greater<int>());
    }
    t.clear();
    for(int i=1;i<=n;i++){
        adj[i].clear();
    }
    for(int i=m-1;i>=0;i--){
        int id=get_mx(v[i][1],v[i][1],v[i][2]);
        if(id!=-1){
            adj[v[id][1]].erase(id);
            adj[v[id][2]].erase(id);
            for(auto it=t.begin();it!=t.end();it++){
                if(*it==id){
                    t.erase(it);
                    break;
                }
            }
        }
        t.push_back(i);
        adj[v[i][1]].insert(i);
        adj[v[i][2]].insert(i);
        r[i]=t;
        sort(all(r[i]));
    }
    int ptr=0;
    int q;cin>>q;
    ll ta=0,tb=0;
    for(int q1=0;q1<q;q1++){
        int x;cin>>x;
        while(ptr<m-1&&v[ptr][0]<=x){
            ptr++;
        }
        DSU dsu(n+1);
        ll ans=0;
        int l1=0,r1=0,cnt=0;
        int ptr1=max(0,ptr-1);
        while(l1<l[ptr1].size()&&r1<r[ptr].size()&&cnt<n-1){
            if(abs(x-v[l[ptr1][l1]][0])<abs(x-v[r[ptr][r1]][0])){
                auto [a1,b1,c1]=v[l[ptr1][l1]];
                if(!dsu.same(b1,c1)){
                    dsu.onion(b1,c1);
                    ans+=abs(x-a1);
                    cnt++;
                }
                l1++;
            }
            else{
                auto [a1,b1,c1]=v[r[ptr][r1]];
                if(!dsu.same(b1,c1)){
                    dsu.onion(b1,c1);
                    ans+=abs(x-a1);
                    cnt++;
                }
                r1++;
            }   
        }
        while(cnt<n-1&&l1<l[ptr1].size()){
            auto [a1,b1,c1]=v[l[ptr1][l1]];
            if(!dsu.same(b1,c1)){
                dsu.onion(b1,c1);
                ans+=abs(x-a1);
                cnt++;
            }
            l1++;
        }
        while(cnt<n-1&&r1<r[ptr].size()){
            auto [a1,b1,c1]=v[r[ptr][r1]];
            if(!dsu.same(b1,c1)){
                dsu.onion(b1,c1);
                ans+=abs(x-a1);
                cnt++;
            }
            r1++;
        }
        cout<<ans<<endl;
    }   


    
    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int32_t main()':
reconstruction.cpp:130:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while(l1<l[ptr1].size()&&r1<r[ptr].size()&&cnt<n-1){
      |               ~~^~~~~~~~~~~~~~~
reconstruction.cpp:130:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         while(l1<l[ptr1].size()&&r1<r[ptr].size()&&cnt<n-1){
      |                                  ~~^~~~~~~~~~~~~~
reconstruction.cpp:150:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         while(cnt<n-1&&l1<l[ptr1].size()){
      |                        ~~^~~~~~~~~~~~~~~
reconstruction.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         while(cnt<n-1&&r1<r[ptr].size()){
      |                        ~~^~~~~~~~~~~~~~
reconstruction.cpp:120:8: warning: unused variable 'ta' [-Wunused-variable]
  120 |     ll ta=0,tb=0;
      |        ^~
reconstruction.cpp:120:13: warning: unused variable 'tb' [-Wunused-variable]
  120 |     ll ta=0,tb=0;
      |             ^~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 28
• Subtask 5: 35 / 35
• Subtask 6: 0 / 23