제출 #754907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754907		definitelynotmee	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	819 ms	29520 KiB

reconstruction

#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

struct edge{
    int a, b, w;
    edge(int x = 0, int y = 0, int z = 0){
        a = x;
        b = y;
        w = z;
    }
    bool operator < (edge other) const{
        if(w == other.w){
            return make_pair(a,b) < make_pair(other.a,other.b);
        }
        return w < other.w;
    }
    bool operator == (edge other) const{
        return a == other.a and b == other.b and w == other.w;
    }

    string print(){
        string ret = to_string(a) + ' ' + to_string(b) + ' ' + to_string(w);
        return ret;
    }
};

struct UnionFind{
    vector<int> pai;

    UnionFind(int n = 0){
        pai = vector<int>(n);
        iota(all(pai),0);
    }

    int find(int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }

    bool onion(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b)
            return 0;
        pai[a] = b;
        return 1;
    }

    bool check(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b)
            return 0;
        return 1;
    }
};

struct MST{
    matrix<edge> g;

    MST(int n = 0){
        g = matrix<edge>(n);
    }

    edge dfs(int id, int last, int target){
        edge def(0,0,2e9);
        if(id == target)
            return edge(0,0,2e9-5);
        // cerr << "id = " << id << endl;
        for(auto [a, viz, w]: g[id]){
            if(viz == last)
                continue;
            // cerr << "aresta " << a << ' ' << viz << endl;
            edge cur = dfs(viz,id,target);
            if(cur < def){
                return min(cur,edge(a,viz,w));
            }
        }
        return def;
    }

    void insert(edge x){
        g[x.a].push_back(x);
        swap(x.a,x.b);
        g[x.a].push_back(x);
    }

    void erase(edge x){
        // cout << x.a << " -> ";
        // for(auto& [a,b,c] : g[x.a]){
            // cout <<b << ' ';
        // }
        // cout << endl;
        g[x.a].erase(find(all(g[x.a]),x));
        swap(x.a,x.b);
        g[x.a].erase(find(all(g[x.a]),x));
    }

    edge update(edge x){
        edge ret = dfs(x.a,-1,x.b);
        // cerr << ret.w << endl;
        if(ret.w <= 1e9)
            erase(ret);

        insert(x);
        if(ret.a > ret.b)
            swap(ret.a,ret.b);

        return ret;
    }

};


int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, m;

    cin >> n >> m;

    vector<edge> v(m);

    for(auto & [a, b, w] : v){
        cin >> a >> b >> w;
        a--,b--;
        if(a > b)
            swap(a,b);
    }

    sort(all(v));

    vector<int> entra(m), sai(m,2e9);

    MST mst(n);

    for(int i = 0; i < m; i++){
        // cerr << i << endl;
        // cerr << v[i].a << ' ' << v[i].b << ' ' << v[i].w << endl;
        edge cur = v[i];

        edge popado = mst.update(cur);

        if(popado.w <= 1e9){
            // cerr << "entrou" << endl;
            int id = lower_bound(all(v),popado)-v.begin();
            int turning_point = (cur.w+popado.w+1)/2;
            entra[i] = turning_point;
            sai[id] = turning_point;
        }
    }

    vector<int> oentra(m), osai(m), ov(m);
    
    auto setup =[&](vector<int> & o, auto& v){
        iota(all(o),0);
        sort(all(o), [&](int a, int b){
            return v[a] < v[b];
        });
    };


    setup(oentra,entra);
    setup(osai,sai);
    setup(ov,v);

    int pentra = 0, psai = 0, pv = 0;

    int q;
    cin >> q;

    ll qtd = 0;
    ll resp = 0;

    while(q--){
        ll x;
        cin >> x;

        
        
        // cerr << "x = " << x << endl;

        while(pentra < m && entra[oentra[pentra]] <= x){
            // cerr << "entra " << v[oentra[pentra]].print() << '\n';
            
            qtd--;
            resp+=v[oentra[pentra]].w;
            pentra++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }
        while(pv < m && v[ov[pv]].w <= x){
            // cerr << "change " << v[ov[pv]].print() << '\n';
            
            qtd+=2;
            resp-=2*v[ov[pv]].w;
            pv++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }
        while(psai < m && sai[osai[psai]] <= x){
            // cerr << "sai " << v[osai[psai]].print() << '\n';
            
            qtd--;
            resp+=v[osai[psai]].w;
            psai++;
            // cerr << "qtd = " << qtd << ", resp = " << resp <<  '\n';
        }

        cout << resp +qtd*x<< '\n';
    }



}

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