Submission #674045

#	Time	Username	Problem	Language	Result	Execution time	Memory
674045		peijar	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2197 ms	40092 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;

struct UnionFind {
  vector<int> id;

  UnionFind() {}
  UnionFind(int N) { id.assign(N, -1); }

  int find(int u) {
    if (id[u] < 0)
      return u;
    return id[u] = find(id[u]);
  }

  bool merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (id[u] > id[v])
      swap(u, v);
    id[u] += id[v];
    id[v] = u;
    return true;
  }
};

struct Edge {
  int u, v, w;

  Edge() {}

  Edge(int a, int b, int c) : u(a), v(b), w(c) {}

  bool operator<(Edge other) const {
    return tuple(w, u, v) < tuple(other.w, other.u, other.v);
  };
};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbAretes;
  cin >> nbSommet >> nbAretes;

  vector<Edge> edges(nbAretes);
  for (auto &[u, v, w] : edges) {
    cin >> u >> v >> w;
    --u, --v;
  }

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

  vector<int> debRight(nbAretes), finRight(nbAretes);
  vector<int> debLeft(nbAretes), finLeft(nbAretes);

  vector<int> usefulEdges;
  for (int iArete = nbAretes - 1; iArete >= 0; --iArete) {
    UnionFind dsu(nbSommet);
    int nxt = -1;
    for (int i : usefulEdges) {
      dsu.merge(edges[i].u, edges[i].v);
      if (dsu.find(edges[iArete].u) == dsu.find(edges[iArete].v)) {
        nxt = i;
        break;
      }
    }

    debRight[iArete] = edges[iArete].w + 1;
    finRight[iArete] = nxt == -1 ? INF : (edges[iArete].w + edges[nxt].w) / 2;

    vector<int> nxtUseful;
    nxtUseful.push_back(iArete);
    for (int i : usefulEdges)
      if (i != nxt)
        nxtUseful.push_back(i);
    usefulEdges = nxtUseful;
  }

  usefulEdges.clear();
  for (int iArete = 0; iArete < nbAretes; ++iArete) {
    UnionFind dsu(nbSommet);
    int nxt = -1;
    for (int i : usefulEdges) {
      dsu.merge(edges[i].u, edges[i].v);
      if (dsu.find(edges[iArete].u) == dsu.find(edges[iArete].v)) {
        nxt = i;
        break;
      }
    }

    finLeft[iArete] = edges[iArete].w;
    debLeft[iArete] =
        nxt == -1 ? 0 : ((edges[iArete].w + edges[nxt].w) / 2 + 1);

    vector<int> nxtUseful;
    nxtUseful.push_back(iArete);
    for (int i : usefulEdges)
      if (i != nxt)
        nxtUseful.push_back(i);
    usefulEdges = nxtUseful;
  }

  vector<tuple<int, int, int>> eventsL, eventsR;
  for (int iArete = 0; iArete < nbAretes; ++iArete) {
    eventsL.emplace_back(debLeft[iArete], 1, iArete);
    eventsL.emplace_back(finLeft[iArete] + 1, -1, iArete);
    eventsR.emplace_back(debRight[iArete], 1, iArete);
    eventsR.emplace_back(finRight[iArete] + 1, -1, iArete);
  }
  sort(eventsL.begin(), eventsL.end());
  sort(eventsR.begin(), eventsR.end());

  int mult = 0, add = 0;

  int posL = 0, posR = 0;
  int nbRequetes;
  cin >> nbRequetes;
  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    int x;
    cin >> x;
    while (posL < (int)eventsL.size() and get<0>(eventsL[posL]) <= x) {
      auto [d, delta, iArete] = eventsL[posL++];
      if (delta == 1)
        mult--, add += edges[iArete].w;
      else
        mult++, add -= edges[iArete].w;
    }
    while (posR < (int)eventsR.size() and get<0>(eventsR[posR]) <= x) {
      auto [d, delta, iArete] = eventsR[posR++];
      if (delta == 1)
        mult++, add -= edges[iArete].w;
      else
        mult--, add += edges[iArete].w;
    }
    cout << x * mult + add << '\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