Submission #1197408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197408		Zero_OP	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1216 ms	19756 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;

struct DSU{
      vector<int> lab;
      DSU(int n) : lab(n, -1) {}
      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      bool join(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            return true;
      }
};

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif //LOCAL

      int N, M;
      cin >> N >> M;
      vector<array<int, 3>> edges;
      for(int i = 0; i < M; ++i){
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            edges.push_back({w, u, v});
      }

      sort(edges.begin(), edges.end());
      vector<int> par(N), depth(N);
      DSU dsu(N);
      vector<vector<int>> adj(N);

      function<void(int, int)> dfs = [&](int u, int e){
            for(auto id : adj[u]) if(id != e){
                  int v = edges[id][1] ^ edges[id][2] ^ u;
                  par[v] = id;
                  depth[v] = depth[u] + 1;
                  dfs(v, id);
            }
      };

      function<void()> rebuild = [&](){
            for(int i = 0; i < N; ++i) par[i] = -1, depth[i] = 0;
            for(int i = 0; i < N; ++i) if(depth[i] == 0) dfs(i, -1);
      };

      vector<int> next(M, -1);
      vector<array<int, 3>> events;
      for(int i = 0; i < M; ++i){
            int w = edges[i][0], u = edges[i][1], v = edges[i][2];

            if(dsu.join(u, v)){
                  adj[u].emplace_back(i);
                  adj[v].emplace_back(i);

                  events.push_back({0, -1, w});
                  events.push_back({w, +1, -w});
                  events.push_back({w, +1, -w});
            } else{
                  int remove_idx = -1;
                  for(int pu = u, pv = v; pu != pv; ){
                        if(depth[pu] < depth[pv]) swap(pu, pv);
                        int cur = par[pu];
                        if(remove_idx == -1 || edges[remove_idx][0] > edges[cur][0]){
                              remove_idx = cur;
                        }
                        pu ^= edges[cur][1] ^ edges[cur][2];
                  }

                  next[remove_idx] = i;
                  int a = edges[remove_idx][1], b = edges[remove_idx][2];
                  adj[a].erase(find(adj[a].begin(), adj[a].end(), remove_idx));
                  adj[b].erase(find(adj[b].begin(), adj[b].end(), remove_idx));
                  adj[u].push_back(i);
                  adj[v].push_back(i);
            }

            rebuild();
      }

      for(int i = 0; i < M; ++i){
            if(next[i] != -1){
                  assert(i < next[i]);
                  int p = (edges[i][0] + edges[next[i]][0] + 1) / 2;
                  events.push_back({p, -1, +edges[i][0]});
                  events.push_back({p, -1, +edges[next[i]][0]});
                  events.push_back({edges[next[i]][0], +1, -edges[next[i]][0]});
                  events.push_back({edges[next[i]][0], +1, -edges[next[i]][0]});
            }
      }

      sort(events.begin(), events.end());

//      for(int i = 0; i < (int)events.size(); ++i){
//            cout << events[i][0] << ' ' << events[i][1] << ' ' << events[i][2] << '\n';
//      }

      int ptr = 0;
      long long a = 0, b = 0; //ax + b
      int Q;
      cin >> Q;
      while(Q--){
            int X;
            cin >> X;
//            cout << "[" << X << "]\n";

            while(ptr < (int)events.size() && events[ptr][0] <= X){
                  a += events[ptr][1];
                  b += events[ptr][2];
                  ++ptr;
            }

//            cout << a << ' ' << b << ' ';
            cout << a * X + b << '\n';
      }

      return 0;
}

/*

4 5
1 2 4
1 4 3
2 4 2
2 3 1
3 4 3
4
1
2
3
4


*/

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