Submission #710437

#	Time	Username	Problem	Language	Result	Execution time	Memory
710437		alvingogo	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	1484 ms	30932 KiB

reconstruction

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct TR{
    int n;
    struct no{
        vector<pair<int,int> > ch;
        pair<int,int> fa={-1,-1};
    };
    vector<no> v;
    void init(int x){
        n=x;
        v.resize(n);
    }
    void add(int a,int b,int c){
        v[a].ch.push_back({b,c});
        v[b].ch.push_back({a,c});
    }
    void del(int a,int b){
        //cout << a << "d" << b << '\n';
        int x=v[a].ch.size();
        for(int i=0;i<x;i++){
            if(v[a].ch[i].fs==b){
                swap(v[a].ch[i],v[a].ch[x-1]);
                break;
            }
        }
        v[a].ch.pop_back();
        x=v[b].ch.size();
        for(int i=0;i<x;i++){
            if(v[b].ch[i].fs==a){
                swap(v[b].ch[i],v[b].ch[x-1]);
                break;
            }
        }
        v[b].ch.pop_back();
    }
    void print(){
        for(int i=0;i<n;i++){
            cout << i << ": ";
            for(auto h:v[i].ch){
                cout << "(" << h.fs << " " << h.sc << ") ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
    void dfs(int r,pair<int,int> f){
        v[r].fa=f;
        for(auto h:v[r].ch){
            if(h!=f){
                dfs(h.fs,{r,h.sc});
            }
        }
    }
    pair<int,pair<int,int> > get(int r){
        if(v[r].fa.fs<0){
            return {-1,{-1,-1}};
        }
        pair<int,pair<int,int> > tt={1e18,{-1,-1}};
        for(;v[r].fa.fs>=0;r=v[r].fa.fs){
            tt=min(tt,{v[r].fa.sc,{v[r].fa.fs,r}});
        }
        del(tt.sc.fs,tt.sc.sc);
        return tt;
    }
}tr;
signed main(){
    AquA;
    int n,m;
    cin >> n >> m;
    vector<pair<int,pair<int,int> > > vp;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--;
        b--;
        vp.push_back({c,{a,b}});
    }
    tr.init(n);
    sort(vp.begin(),vp.end());
    vector<pair<int,pair<int,int> > > gg;
    int a=0,b=0;
    //f(x)=ax+b
    multiset<int> s;
    for(auto h:vp){
        int x=h.sc.fs,y=h.sc.sc;
        for(int i=0;i<n;i++){
            tr.v[i].fa={-1,-1};
        }
        tr.dfs(x,{-1,-1});
        auto u=tr.get(y);
        tr.add(x,y,h.fs);
        //cout << h.fs << " " << u.fs << endl;
        //tr.print();
        if(u.fs>=0){
            if(h.fs==u.fs){
                continue;
            }
            int t=(h.fs+u.fs+1)/2;
            gg.push_back({t,{h.fs,u.fs}});
        }
        else{
            a--;
            b+=h.fs;
        }
        gg.push_back({h.fs,{-2,-2*h.fs}});
    }
    sort(gg.begin(),gg.end());
    int q;
    cin >> q;
    int l=0;
    int uu=gg.size();
    for(int i=0;i<q;i++){
        int x;
        cin >> x;
        while(l<uu && gg[l].fs<=x){
            auto c=gg[l].sc.fs,d=gg[l].sc.sc;
            if(c<0){
                a+=2;
                b+=d;
            }
            else{
                a-=2;
                b+=c+d;
            }
            l++;
        }
        cout << a*x+b << "\n";
    }
    return 0;
}

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