Submission #999478

#	Time	Username	Problem	Language	Result	Execution time	Memory
999478		vladilius	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5072 ms	427608 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const int inf = 1e9 + 5;

struct ST{
    vector<vector<pii>> g;
    vector<pii> ed;
    vector<int> gd;
    int n, m, A;
    bool type;
    ST(int ns, int ms){
        n = ns;
        m = ms;
        g.resize(n + 1);
        ed.resize(m + 1);
    }
    void set_mini(){
        A = m + 1;
        type = 1;
    }
    void set_maxi(){
        A = 0;
        type = 0;
    }
    int f(int x, int y){
        if (type){
            return min(x, y);
        }
        return max(x, y);
    }
    vector<pii> st;
    bool ind;
    void dfs(int v, int pr, int pre, int& t){
        // cout<<"дідько "<<v<<" "<<pr<<" "<<t<<" "<<"\n";
        if (ind) return;
        st.pb({v, pre});
        if (v == t){
            ind = 1;
            return;
        }
        for (auto [i, j]: g[v]){
            if (i == pr) continue;
            dfs(i, v, j, t);
        }
        if (ind) return;
        st.pop_back();
    }
    void add(int x, int y, int i){
        ed[i] = {x, y};
        st.clear();
        ind = 0;
        dfs(x, 0, A, y);
        if (st.size() > 1){
            int mn = A;
            for (auto [j, ii]: st) mn = f(mn, ii);
            auto [u, v] = ed[mn];
            gd.erase(find(gd.begin(), gd.end(), mn));
            for (int i = 0; i < g[u].size(); i++){
                if (g[u][i].ff == v){
                    g[u].erase(g[u].begin() + i);
                    break;
                }
            }
            for (int i = 0; i < g[v].size(); i++){
                if (g[v][i].ff == u){
                    g[v].erase(g[v].begin() + i);
                    break;
                }
            }
        }
        g[x].pb({y, i});
        g[y].pb({x, i});
        gd.pb(i);
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            g[i].clear();
        }
        ed.clear();
        gd.clear();
    }
};

struct dsu{
    vector<int> sz, p;
    int n;
    ll W;
    dsu(int ns){
        n = ns;
        p.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
        W = 0;
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y, int w){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        p[x] = y;
        sz[y] += sz[x];
        W += w;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m; cin>>n>>m;
    vector<arr3> ed = {{0, 0, 0}};
    for (int i = 1; i <= m; i++){
        int a, b, w; cin>>a>>b>>w;
        ed.pb({a, b, w});
    }
    ed.pb({0, 0, inf});
    
    auto cmp = [&](arr3& x, arr3& y){
        return x[2] < y[2];
    };
    sort(ed.begin(), ed.end(), cmp);
    
    vector<int> actl[m + 2];
    ST T(n, m);
    T.set_mini();
    for (int i = 1; i <= m; i++){
        T.add(ed[i][0], ed[i][1], i);
        actl[i] = T.gd;
    }
    
    T.clear();
    T.set_maxi();
    vector<int> actr[m + 2];
    for (int i = m; i > 0; i--){
        T.add(ed[i][0], ed[i][1], i);
        actr[i] = T.gd;
    }
    
    int q; cin>>q;
    vector<pii> qs;
    for (int i = 1; i <= q; i++){
        int x; cin>>x;
        qs.pb({x, i});
    }
    sort(qs.begin(), qs.end());

    vector<ll> out(q + 1);
    int j1 = 0;
    for (int i = 0; i <= m; i++){
        vector<int> edg;
        for (auto p: actl[i]) edg.pb(p);
        for (auto p: actr[i + 1]) edg.pb(p);
        
        int l = ed[i][2], r = ed[i + 1][2] - 1;
        int j2 = j1;
        while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
            j2++;
        }
        while (j1 < j2){
            int x = qs[j1].ff;
            vector<arr3> ed1;
            for (int p: edg) ed1.pb({ed[p][0], ed[p][1], abs(ed[p][2] - x)});
            sort(ed1.begin(), ed1.end(), cmp);
            dsu T(n);
            for (auto [x, y, w]: ed1) T.unite(x, y, w);
            out[qs[j1].ss] = T.W;
            j1++;
        }
    }
    
    for (int i = 1; i <= q; i++) cout<<out[i]<<"\n";
}

Compilation message (stderr)

reconstruction.cpp: In member function 'void ST::add(int, int, int)':
reconstruction.cpp:65:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int i = 0; i < g[u].size(); i++){
      |                             ~~^~~~~~~~~~~~~
reconstruction.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (int i = 0; i < g[v].size(); i++){
      |                             ~~^~~~~~~~~~~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:172:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         while (j2 < qs.size() && l <= qs[j2].ff && qs[j2].ff <= r){
      |                ~~~^~~~~~~~~~~

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