Submission #1087683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087683		vladilius	Reconstruction Project (JOI22_reconstruction)	C++17	70 / 100	5093 ms	427832 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;
const int N = 5e2;

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){
        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{
    int sz[N + 1], p[N + 1], n;
    ll W;
    dsu(int ns){
        n = ns;
    }
    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;
    }
    void clear(){
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
        W = 0;
    }
};
 
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 T1(n, m);
    T1.set_mini();
    for (int i = 1; i <= m; i++){
        T1.add(ed[i][0], ed[i][1], i);
        actl[i] = T1.gd;
        reverse(actl[i].begin(), actl[i].end());
    }
    
    T1.clear();
    T1.set_maxi();
    vector<int> actr[m + 2];
    for (int i = m; i > 0; i--){
        T1.add(ed[i][0], ed[i][1], i);
        actr[i] = T1.gd;
        reverse(actr[i].begin(), actr[i].end());
    }
    
    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;
    dsu T(n);
    for (int i = 0; i <= m; i++){
        vector<int>& edg1 = actl[i], edg2 = actr[i + 1];
        
        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;
            int i1 = 0, i2 = 0;
            T.clear();
            while (i1 < edg1.size() || i2 < edg2.size()){
                if (i1 == edg1.size()){
                    int j = edg2[i2];
                    T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
                    i2++;
                    continue;
                }
                if (i2 == edg2.size()){
                    int j = edg1[i1];
                    T.unite(ed[j][0], ed[j][1], abs(ed[j][2] - x));
                    i1++;
                    continue;
                }
                int v1 = abs(ed[edg1[i1]][2] - x);
                int v2 = abs(ed[edg2[i2]][2] - x);
                if (v1 < v2){
                    int j = edg1[i1];
                    T.unite(ed[j][0], ed[j][1], v1);
                    i1++;
                }
                else {
                    int j = edg2[i2];
                    T.unite(ed[j][0], ed[j][1], v2);
                    i2++;
                }
            }
            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){
      |                ~~~^~~~~~~~~~~
reconstruction.cpp:179:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                    ~~~^~~~~~~~~~~~~
reconstruction.cpp:179:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |             while (i1 < edg1.size() || i2 < edg2.size()){
      |                                        ~~~^~~~~~~~~~~~~
reconstruction.cpp:180:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |                 if (i1 == edg1.size()){
      |                     ~~~^~~~~~~~~~~~~~
reconstruction.cpp:186:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |                 if (i2 == edg2.size()){
      |                     ~~~^~~~~~~~~~~~~~

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