oj.uz

답안 #858696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858696 2023-10-09T04:44:44 Z NeroZein 조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2) C++17
0 / 100
 4 ms 15196 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e5 + 5;

long long ans;
set<int> r[N];
int p[N], sz[N];
set<pair<int, int>> in[N], out[N]; 

int get(int x) {
  return p[x] = (p[x] == x ? x : get(p[x])); 
}

void merge(int x, int y) {
  x = get(x), y = get(y);
  if (x == y) {
    return;
  }
  //deb(ans) deb(x) deb(y) deb(in[x]) deb(in[y]) deb(out[x]) deb(out[y]) cout << '\n';
  auto f = in[x].lower_bound(make_pair(y, 0));
  while (f != in[x].end() && f->first == y) {
    ans -= sz[x];
    r[x].erase(f->second); 
    out[y].erase(make_pair(x, f->second)); 
    f = in[x].erase(f); 
  }
  f = in[y].lower_bound(make_pair(x, 0)); 
  while (f != in[y].end() && f->first == x) {
    ans -= sz[y];
    r[y].erase(f->second); 
    out[x].erase(make_pair(y, f->second)); 
    f = in[y].erase(f); 
  }
  
  if (in[x].size() + out[x].size() < in[y].size() + out[y].size()) {
    swap(x, y); 
  }
  //deb(ans) deb(x) deb(y) deb(in[x]) deb(in[y]) deb(out[x]) deb(out[y]) cout << '\n';
  ans -= (long long) in[x].size() * sz[x];
  ans -= (long long) in[y].size() * sz[y];
  ans -= (long long) sz[x] * (sz[x] - 1); 
  ans -= (long long) sz[y] * (sz[y] - 1); 
  for (auto [i, j] : in[y]) {
    if (!in[x].count({i, j})) {
      in[x].emplace(i, j); 
      r[x].insert(j); 
    }
  }
  p[y] = x;
  sz[x] += sz[y];
  ans += (long long) in[x].size() * sz[x];
  ans += (long long) sz[x] * (sz[x] - 1);
  //deb(ans) deb(x) deb(y) deb(in[x]) deb(in[y]) deb(out[x]) deb(out[y]) cout << '\n';
  vector<int> to_merge; 
  for (auto [i, j] : out[y]) {
    in[i].erase(make_pair(y, j));
    in[i].emplace(x, j); 
    out[x].emplace(i, j); 
    f = in[x].lower_bound(make_pair(i, 0));
    if (f != in[x].end() && f->first == i) {
      to_merge.push_back(i); 
    }
  }
  //cout << '\n';
  for (int i : to_merge) {
    merge(x, i); 
  }
}

void add(int x, int y) {
  int px = get(x), py = get(y);
  if (px == py || r[py].count(x)) {
    return;
  }
  ans += sz[py];
  r[py].insert(x);
  in[py].emplace(px, x);
  out[px].emplace(py, x);
  auto f = in[px].lower_bound(make_pair(py, 0)); 
  if (f != in[px].end() && f->first == py) {
    merge(px, py); 
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  iota(p + 1, p + 1 + n, 1); 
  fill(sz + 1, sz + 1 + n, 1); 
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    cout << ans << '\n'; 
  }
  return 0;
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Incorrect 3 ms 15192 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Incorrect 3 ms 15192 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 83.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15196 KB Output is correct
5 Incorrect 3 ms 15192 KB Output isn't correct
6 Halted 0 ms 0 KB -