Submission #812731

#	Time	Username	Problem	Language	Result	Execution time	Memory
812731		peijar	Bridges (APIO19_bridges)	C++17	59 / 100	3059 ms	8896 KiB

bridges

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

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

struct UnionFind {
  vector<int> id;
  stack<tuple<int, int, int, int>> stk;

  UnionFind(int N) : id(N, -1) {}

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

  void merge(int a, int b) {
    a = find(a), b = find(b);

    stk.emplace(a, b, id[a], id[b]);
    if (a == b)
      return;

    if (id[a] > id[b])
      swap(a, b);
    id[a] += id[b];
    id[b] = a;
  }

  void rollback() {
    auto [a, b, ida, idb] = stk.top();
    stk.pop();
    id[a] = ida, id[b] = idb;
  }
};
struct Requete {
  int type, sommet, poids, iRequete;
};

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

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

  vector<pair<int, int>> edges(nbAretes);

  vector<int> weight(nbAretes);
  for (int i = 0; i < nbAretes; ++i) {
    cin >> edges[i].first >> edges[i].second >> weight[i];
    --edges[i].first;
    --edges[i].second;
  }

  vector<Requete> requetes;
  int nbRequetes;
  cin >> nbRequetes;
  vector<int> sol(nbRequetes, -1);
  vector<int> idArete(nbAretes);

  auto process = [&]() {
    UnionFind dsu(nbSommet);
    vector<bool> changes(nbAretes);
    for (Requete req : requetes)
      if (req.type == 1)
        changes[req.sommet] = true;
    vector<int> posAnswer;
    for (int i = 0; i < (int)requetes.size(); ++i)
      if (requetes[i].type == 2)
        posAnswer.push_back(i);

    sort(posAnswer.begin(), posAnswer.end(),
         [&](int i, int j) { return requetes[i].poids > requetes[j].poids; });

    vector<int> posStatic;
    for (int i = 0; i < nbAretes; ++i)
      if (!changes[i])
        posStatic.push_back(i);
    vector<int> posChange;
    for (int i = 0; i < nbAretes; ++i)
      if (changes[i])
        posChange.push_back(i);
    for (int i = 0; i < (int)posChange.size(); ++i)
      idArete[posChange[i]] = i;
    sort(posStatic.begin(), posStatic.end(),
         [&](int i, int j) { return weight[i] > weight[j]; });

    auto getId = [&](int i) { return idArete[i]; };

    int curStat = 0;

    for (int i : posAnswer) {
      while (curStat < (int)posStatic.size() and
             weight[posStatic[curStat]] >= requetes[i].poids) {
        dsu.merge(edges[posStatic[curStat]].first,
                  edges[posStatic[curStat]].second);
        ++curStat;
      }
      vector<bool> seen(posChange.size());
      int cntPop = 0;
      for (int j = i - 1; j >= 0; --j)
        if (requetes[j].type == 1 and !seen[getId(requetes[j].sommet)]) {
          seen[getId(requetes[j].sommet)] = true;
          if (requetes[j].poids >= requetes[i].poids) {
            dsu.merge(edges[requetes[j].sommet].first,
                      edges[requetes[j].sommet].second);
            ++cntPop;
          }
        }
      for (int j = 0; j < (int)posChange.size(); ++j)
        if (!seen[j] and weight[posChange[j]] >= requetes[i].poids) {
          int iArete = posChange[j];
          dsu.merge(edges[iArete].first, edges[iArete].second);
          cntPop++;
        }

      sol[requetes[i].iRequete] = -dsu.id[dsu.find(requetes[i].sommet)];

      for (int j = 0; j < cntPop; ++j)
        dsu.rollback();
    }

    for (Requete req : requetes)
      if (req.type == 1)
        weight[req.sommet] = req.poids;
    requetes.clear();
  };

  for (int i = 0; i < nbRequetes; ++i) {
    int t, u, w;
    cin >> t >> u >> w;
    --u;
    requetes.push_back(Requete{t, u, w, i});
    if ((int)requetes.size() * (int)requetes.size() >= nbRequetes)
      process();
  }
  if (!requetes.empty())
    process();
  for (int x : sol)
    if (x != -1)
      cout << x << '\n';
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27