CF 588 C. Konrad and Company Evaluation

https://codeforces.com/contest/1229/problem/C

Straight forward solution runs in O(Q sqrt(N)). Let's prove this fact by potential analysis. We define the potential of this problem as the sum of the degrees of the vertices whose in-degree is greater than sqrt(N). When we choose a small vertex, an actual time is at most sqrt(N) and the potential increases by sqrt(N), so its time complexity is amortized O(sqrt(N)). When we choose a large vertex, an actual time is equal to its in-degree, but the potential decreases by the same amount, so the sum of them becomes zero. Moreover, the potential increases at most sqrt(N) because there are at most sqrt(N) vertices of degree sqrt(N) or greater, so the amortized cost is upto O(sqrt(N)). Therefore, the total time complexity is amortized O(Q sqrt(N)).


Source Code

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, M; cin >> N >> M;
  vector<vector<int>> in(N);
  vector<vector<int>> out(N);
  vector<int> deg(N);
  rep(i, M) {
    int a, b; cin >> a >> b; a--; b--;
    if (a < b) swap(a, b);
    in[b].push_back(a);
    out[a].push_back(b);
    deg[a]++;
    deg[b]++;
  }
  ll ans = 0;
  rep(i, N) for (int j : out[i]) ans += out[j].size();
  int Q; cin >> Q;
  cout << ans << '\n';
  while (Q--) {
    int u; cin >> u; u--;
    ans -= (ll)in[u].size() * (deg[u] - in[u].size());
    for (int v : in[u]) {
      ans -= in[v].size();
      in[v].push_back(u);
      ans += deg[v] - in[v].size();
    }
    in[u].clear();
    cout << ans << '\n';
  }
}