oj.uz

답안 #1045490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1045490 2024-08-06T03:14:30 Z abczz 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 4 ms 22876 KB 
#include <iostream>
#include <vector>
#include <map>
#define ll long long

using namespace std;

vector <ll> V[100000];
map <ll, ll> adj[100000], radj[100000], cyc[100000], rcyc[100000];
ll n, m, a, b, f, P[100000], sz[100000];

ll dsu(ll u) {
  if (P[u] == u) return u;
  else return P[u] = dsu(P[u]);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i=0; i<n; ++i) P[i] = i, sz[i] = 1, V[i].push_back(i);
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    b = dsu(b);
    if (!adj[a].count(b)) {
      ++adj[a][b];
      ++radj[b][a];
      f += sz[b];
    }
    a = dsu(a);
    if (a == b) {
      cout << f << '\n';
      continue;
    }
    ++cyc[a][b];
    ++rcyc[b][a];
    if (!cyc[b].count(a)) {
      cout << f << '\n';
      continue;
    }
    if (sz[a] < sz[b]) swap(a, b);
    for (auto [x, y] : cyc[b]) {
      ++cyc[a][x];
      ++rcyc[x][a];
    }
    for (auto [x, y] : rcyc[b]) {
      ++rcyc[a][x];
      ++cyc[x][a];
    }
    cyc[b].clear();
    rcyc[b].clear();
    for (auto [x, y] : radj[b]) {
      if (dsu(x) == a || adj[x].count(a)) f -= sz[b];
      else {
        ++adj[x][a];
        ++radj[a][x];
        f += sz[a];
        f -= sz[b];
      }
      adj[x].erase(b);
    }
    radj[b].clear();
    for (auto u : V[b]) {
      if (adj[u].count(a)) {
        adj[u].erase(a);
        radj[a].erase(u);
        f -= sz[a];
      }
      V[a].push_back(u);
    }
    V[b].clear();
    f += radj[a].size() * sz[b];
    f += sz[a] * sz[b] * 2;
    sz[a] += sz[b];
    P[b] = a;
    cout << f << '\n';
  }
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -